友愛数は、2つの自然数の組でできていて、
一つの自然数の(自分自身の数を除いた)約数の和がもう一つの数になるという数字です。
一番小さい数字は220と284で、
220の約数は、1,2,4,5,10,11,20,22,44,55,110でこの合計が284
284の約数は、1,2,4,71,141でこの合計が220
ということになります。
計算する時に約数を全部求めないといけないので、なかなか大変だと思います。
ある自然数aに対して、√aまでの約数を求めておけば、あとは割り算で求められるのですが、もっといい方法はないのかということを考えます。
ある自然数aが互いに素である2数p、qの積で表される時、約数の和S(a)は (このSは自分自身も含みます。)
S(a)=S(pq)=S(p)S(q)と表すことができます。
つまり、小さい方から順に約数リストを作るのですが、
互いに素である2数の積にできれば、すでに調べた値の積で計算できるということになります。
もし、
aが素数なら、分けることは出来ませんが、S(a)=a+1となりますので、素数表を作っておくと簡単です。
aがpのk乗であるような場合、2数に分けられませんが、S(p^(k-1))+aで求めることができます。
aが偶数なら2で割れるだけ割っておいて、商と2^kに分けることができます。
奇数は3から順に調べるしかなさそうですが、√aまで調べればいいはずです。
こんな感じで調べていくと、
pythonでも1億まで調べることができました。
かかった時間は6分程度です。
1億までの素数表はエラトステネスの篩法が優秀で、1秒ぐらいでできてしまいます。
最終的に作る素数表もそれほど大きくないのですが、
約数テーブルを1億まで作るとさすがにメモリが。。。。。
ということで、ここまででした。