自然数nの約数の和をσ(n)とする。
異なる2つの自然数m、nについて、各々の約数の和より自分自身を引いたものが、
互いに他方と等しくなる時、すなわち、
σ(m)−m=n
σ(n)−n=m
が成り立つ時、これら2数を友愛数(または親和数)と呼ぶ。
例えば、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 という例は聖書にも出てくるという有名な例である。
以下 1010以下の友愛数の組をしらみつぶしに求めてみる。
自然数nが、
n=p1e1・p2e2・……・pkek
と素因数分解されるとき、nの約数の和σ(n)は以下の式で表される。
σ(n)=a1・a2・……・ak
ただし、
pkek+1−1 ak= ------------ pk−1
特に、
pkek+1−1 ------------ = pkek + …… + pk2 + pk + 1 pk−1
となるので、n=peのとき、
σ(n)= pe + …… + p2 + p + 1
となる。
素因数分解の途中では、この式の方が扱いやすい。
手順は以下のとおり。
w=w×p+1とする。
n=n/p
n=p1e1・p2e2・……・pkekのときの σ(n) は以下のようにして求める。
s=s×wとする
プログラムは以下のとおりとなる。
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)
これを利用して、友愛数探査プログラムを組んでみる。
前 | この章の目次 | 次 |
---|