約数の個数の総和(数える向きの交換)

方針

解答

⓪ 発想 — どう考え始めるか。 $d(k)$ を20個計算して足しても届く。だが、この和の正体を見抜くと一気に整う。

$d(k)$ は「$k$ の約数 $j$」の個数。だから和全体は、組 $(j,k)$($j$ は $k$ の約数、$k\le 20$)の総数を数えている。

この組の集まりを、$k$ ごと(縦)ではなく $j$ ごと(横)に数え直す。$j$ を固定すると、$j$ が約数になる $k\le 20$ とは $j$ の倍数のことで、その個数は $\left[\frac{20}{j}\right]$ 個。数える向きの交換(二重数え)が急所だ。

① 対応を確かめる。 「$k$ の約数として $j$ を数える」ことと「$j$ の倍数として $k$ を数える」ことは、同じ組 $(j,k)$ を逆から見ているだけ。だから2つの総和は等しい。

② $j$ ごとに足す。

$$\sum _{j=1}^{20}\left[\frac{20}{j}\right]=20+10+6+5+4+3+2+2+2+2+\underset{j=11〜20}{\underbrace{1+\cdots +1}}$$

前半($j=1$ 〜 $10$)の和は $20+10+6+5+4+3+2+2+2+2=56$、後半は $1\times 10=10$。よって

$$\sum _{k=1}^{20}d(k)=56+10=66$$

③ 検算。 素直に $d(1)+d(2)+\cdots +d(20)=1+2+2+3+2+4+2+4+3+4+2+6+2+4+4+5+2+6+2+6=66$ で一致する。

まとめ: 「(約数の個数)の和 =(倍数の個数)の和」— 格子状に並んだ組を縦に数えるか横に数えるかの交換だ。割り切りの関係を組 $(j,k)$ の表として見る目は、数列と整数にまたがる広い応用をもつ。

発展 — 一歩先へ。 ${\sum }_{k\le N}d(k)={\sum }_{j\le N}\left[\frac{N}{j}\right]$ は、$N$ が大きいとおよそ $N\log N$ で成長する(調和級数の形)。つまり「$N$ 以下の数は平均して約 $\log N$ 個の約数をもつ」。双曲線法はこの平均の精密化(ディリクレの約数問題)への入り口で、大学以降の解析的整数論に直結している。

別解

対称性で半分だけ数える(双曲線法)。 組 $(j,k)$($j\mid k$)は、$k=jm$ と書けば「$jm\le 20$ を満たす自然数の組 $(j,m)$」と同じもの。つまりこの和は、双曲線 $jm=20$ の下にある格子点の個数だ。

この見方の御利益は対称性にある。$(j,m)$ と $(m,j)$ は対で現れるから、$j\le 4$($4^2\le 20<5^2$)の部分だけ数えて2倍し、両方 $4$ 以下の正方形部分(重複)を引けばよい:

$$\#=2\sum _{j=1}^4\left[\frac{20}{j}\right]-4^2=2(20+10+6+5)-16=82-16=66$$

$j$ を $20$ まで走らせる(本解の交換)代わりに、$4$ までで済んだ。

$N$ が大きいほどこの節約は効いて、$\sqrt{N}$ 程度の項数で ${\sum }_{k\le N}d(k)$ が数えられる。「対称な表は半分だけ数えて折り返す」— 二重数えの上級技だ。