10,000未満の友愛数を全て足すといくつになるか
友愛数とは数のペアで、自分自身を除く約数の和がお互いに等しいものをいう。
まずは何も考えずにスタンダードに攻めてみる。
これで任意の数の約数の和が求められるので、あとは [1..10000] をfilter [友愛数の条件] してあげれば、友愛数のリストを得ることができる。
しかしこれは若干遅い。もう少し早くする方法はないだろうか。
本質的ではないが、ここでもちょっとした数学の知識を使うことで、少しだが改善することができた。
整数nが n = p^a q^b r^c ... と素因数分解される時、nの（自分自身を含む）約数の和は
p^(a+1)/(p-1) * q^(b+1)/(q-1) * r^(c+1)/(r-1) * ...
で求められる。
p^(a+1)/(p-1) * q^(b+1)/(q-1) * r^(c+1)/(r-1) * ...
で求められる。
これは一見すごいように見えて、普通に高校数学の範囲で確かめることができる。以下はこれを利用した。が、はじめのものに対して3倍ほど早くなるにとどまった。
なお、上でimport している module (Euler) は、今後のために再利用しそうな関数を集めていくためのものである。今回はfactorizationを使用した。
本質的に計算を早めるためには、重複している評価を省くことを考える必要がある。例えば12の約数は6の約数と6の約数の各々に2を掛けた数になるはずである。[a,b,c...]がnの約数なら、n*mの約数は [a,b,c,...,am,bm,cm,...]を含む。このことを上手く使えば、約数の評価をもっと高速化できる…気がする。気がするだけで実行していないのは、考えるうちに迷路にハマってしまったからだ。またいずれ、気を取り直して挑戦しようと思う。
★
