PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 95 / 友愛鎖

ある数の真の約数とは,それ自身を除く約数すべてである。たとえば 28 の真の約数は 1, 2, 4, 7, 14 である。

220 の真の約数の和は 284 で,284 の真の約数の和は 220 となっており,二つの数が鎖をなしている。このため,220 と 284 は友愛数と呼ばれる。

さらに長い鎖はあまり知られていないだろう。たとえば 12496 から始めると 5 つの数の鎖をなす。

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

この鎖は出発点に戻っているため,友愛鎖と呼ばれる。

いずれの要素も 1,000,000 を超えない最長の友愛鎖の最小のメンバーを求めよ。

Problem 95 - Project Euler


問題文の指示通りに真の約数の和のリストを作ります。リストの作成を打ち切る条件は,真の約数の和が「0になる」「10^6 を超える」「リストに含まれているのと同じ数になる」です。

このチェックをパスしたリストに対して「出発点に戻っているかどうか」を調べました。