まず、N＝24について考えてみます。

N＝24＝ $2^3\cdot3^1$ で、約数をすべて列挙すると、{1,2,3,4,6,8,12,24}で約数の個数は、8コで約数すべての和は60です。

次に、N＝24・3＝72について考えてみます。

N＝ $2^3\cdot3^2$ で、約数をすべて列挙すると、{1,2,3,4,6,8,9,12,18,24,36,72}で約数の個数は、12コで、約数のすべての和は195です。

これら3つから、約数の個数と約数のすべての和について考えてみます。

・N＝24のとき、{1,2,3, $2^2$ , $2\cdot3$ , $2^3$ , $2^2\cdot3$ , $2^3\cdot3$ }で、

$2^0$ は、1,3

$2^1$ は2, $2\cdot3$

$2^2$ は $2^2$ , $2^2\cdot3$

$2^3$ は $2^3$ , $2^3\cdot3$ に含まれていることが分かります。

つまり、 $2^k$ (0≦k≦3)は3の約数(1,3)とすべてかけられています。

逆に、 $3^0$ は1,2, $2^2$ , $2^3$

$3^1$ は3, $2\cdot3$ , $2^2\cdot3$ , $2^3\cdot3$ に含まれていますから、 $3^l$ (0≦l≦1)は2の約数(1,2, $2^2$ , $2^3$ )とすべてかけられています。

以上から約数の個数はN= $2^3\cdot3^1$ のべき乗部分に注目して、(1+3)(1+1)=4・2=8コと求められます。

和は、 $(2^0+2^1+2^2+2^3)(3^0+3^1)=15\cdot4=60$ となります。

・N=72= $2^3\cdot3^2$ のとき、{1,2,3,4,6,8,9,12,18,24,36,72}

つまり、{1,2,3, $2^2,2\cdot3,2^3,\underline{3^2},2^2\cdot3,\underline{2\cdot3^2},2^3\cdot3,\underline{2^2\cdot3^2},\underline{2^3\cdot3^2}$ }

＿(傍線部)はN=24に含まれなかった約数です。＿(傍線部)も $2^0,2^1,2^2,2^3$
すべてかけられているので先程と同様に考えると、(1+3)(1+1+1)=(1+3)(1+2)=4・3=12コで、和は $(2^0+2^1+2^2+2^3)(3^0+3^1+3^2)=15\cdot13=195$ です。

■JMO(日本数学オリンピック)の予選の問題ですが、約数の個数という面で楽しんで頂けないでしょうか？

結局、 $(1+q_1)(1+q_2)\dots(1+q_n)$ をm=10, $q_i=1$ (1≦i≦m)として、重複を2で割ったのが本問でした。

ここまでくれば、アルゴリズムが見えてきますね。

$P_k$ (1≦k≦m)を素数として、 $N=P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}$ と表されたNの約数の個数は、 $(1+q_1)(1+q_2)\dots(1+q_m)$

約数の総和は、 $(1+P_1+\dots+P_1^{q_1})(1+P_2+\dots+P_2^{q_2})\dots(1+P_m+\dots+P_m^{q_m})$ と一般化できます。

さて、小手調べに以下の問題にとりくんでみよう！

▶問1

ある整数の約数をすべて足すと168になり、約数の逆数をすべて足すと、2.8になる整数を求めよ。(有名問題)

解　 $N=P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}$ とする。

$S=(1+P_1+\dots +P_1^{q_1})(1+P_2+\dots +P_2^{q_2})\dots (1+P_m+\dots +P_m^{q_m})=168$

$T=1+\frac{1}{P_1}+\frac{1}{q_1}+\dots +\frac{1}{P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}}=2.8\rightleftharpoons \frac{P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}+\dots +1}{P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}}=2.8 \rightleftharpoons\frac{S}{N}=2.8 \rightleftharpoons N=\frac{168}{2.8}=\frac{1680}{28}=60$