1. 約数の和

定義

自然数ｎの約数の和をσ(n)とする。
異なる２つの自然数ｍ、ｎについて、各々の約数の和より自分自身を引いたものが、
互いに他方と等しくなる時、すなわち、

σ(m)−ｍ＝ｎ
σ(n)−ｎ＝ｍ

が成り立つ時、これら２数を友愛数（または親和数）と呼ぶ。
例えば、220 と 284 は、この条件を満たす。

それぞれの約数

220 : 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220
284 : 1, 2, 4, 71, 142, 284

それぞれの約数の和（ただし、自分自身は除く）

220 : 1＋2＋4＋5＋10＋11＋20＋22＋44＋55＋110＝284
284 : 1＋2＋4＋71＋142＝220

ちなみにこの 220 と 284 という例は聖書にも出てくるという有名な例である。

以下 10¹⁰以下の友愛数の組をしらみつぶしに求めてみる。

約数の和

自然数ｎが、

ｎ＝p₁^e₁・p₂^e₂・……・p_k^e_k

と素因数分解されるとき、ｎの約数の和σ(ｎ)は以下の式で表される。

σ(ｎ)＝ａ₁・ａ₂・……・ａ_k

ただし、

       pkek＋１−１
ａk＝ ------------
         pk−１

特に、

 pkek＋１−１
------------ ＝ pkek ＋ …… ＋ pk2 ＋ pk ＋ １
   pk−１

となるので、ｎ＝ｐ^eのとき、

σ(ｎ)＝ p^e ＋ …… ＋ p² ＋ ｐ ＋ １

となる。

素因数分解の途中では、この式の方が扱いやすい。

プログラム

手順は以下のとおり。

1. ｗ＝１とする（ｗにσ(ｎ)の値が計算される）
2. ｐ＝prmdiv(ｎ)
   ｐ｜ｎのとき、

   ｗ＝ｗ×ｐ＋１
   ｎ＝ｎ／ｐ

   とする。
3. ｐがｎを割り切らないなら、終了
   （ｗに p^ｅ ＋ …… ＋ p² ＋ ｐ ＋ １の値がセットされる）
4. goto ２

ｎ＝p₁^e₁・p₂^e₂・……・p_k^e_kのときの σ(ｎ) は以下のようにして求める。

1. ｓ＝１とする（ｓにσ(ｎ)の値が計算される）
2. ｐをｎの最小因数とする。ｐ＝１なら終了
3. 上の１．〜４．を繰り返す。上の３．が成り立ったとき、

   ｓ＝ｓ×ｗ

   とする
4. goto ２

プログラムは以下のとおりとなる。

10   fnSigma(N)
20   local S,W,P
30   S=1
40   W=1:P=prmdiv(N)
50   if N@P=0 then W=W*P+1:N=N\P:goto 50 else S=S*W
60   if N>1 then 40 else return(S)

これを利用して、友愛数探査プログラムを組んでみる。