約数関数の問題
初めに
始めに、約数関数についての定義をしておきます。
自然数$n$に対して、約数関数$σ_x(n)$とは、$n$の正の約数$d$の$x$乗和を値に取る関数である：
\begin{eqnarray}
\sigma_x(n) &=& \sum_{d|n}d^x
\end{eqnarray}
特に、$x=0$のとき$σ_0(n)$は$n$の正の約数の個数を表し、ここでは$d(n)$と表す。$x=1$のとき$σ_1(n)$は$n$の正の約数の総和であり、単に省略して$σ(n)$と表す場合もある。
また、約数関数$σ_x(n)$の$k$回反復を
\begin{eqnarray}
\sigma_x^k(n):=\underbrace{\sigma_x(\cdots(\sigma_x}_{k}(n)\cdots)
\end{eqnarray}
と書く。
それでは、今回扱う問題について考えていきましょう。
今回の問題
この問題はLINEの オープンチャット「数学同好会」 で、@生ゴミ生グミ生ナマコ【中二】 という人物が送ってきたTwitterのDMの画像に書かれていた問題です。
よって誰が発案者なのか不明です。
それがこちら
\begin{eqnarray}
d(\sigma(n)) = n
\end{eqnarray}
が成り立つ自然数は、$n=1,2,3,6$
のみである。
では、実際に1~10についてやってみましょうか
\begin{eqnarray}
\sigma(1) &=& 1 \quad &d(1) &=& 1 \\
\sigma(2) &=& 3 \quad &d(3) &=& 2 \\
\sigma(3) &=& 4 \quad &d(4) &=& 3 \\
\sigma(4) &=& 7 \quad &d(7) &=& 2 \\
\sigma(5) &=& 6 \quad &d(6) &=& 4 \\
\sigma(6) &=& 12 \quad &d(12) &=& 6 \\
\sigma(7) &=& 8 \quad &d(8) &=& 4 \\
\sigma(8) &=& 15 \quad &d(15) &=& 4 \\
\sigma(9) &=& 13 \quad &d(13) &=& 2 \\
\sigma(10) &=& 18 \quad &d(18) &=& 6 \\
\end{eqnarray}
確かに、$n=1\sim10$では$n=1,2,3,6$のみ成り立っています。
それでは証明していきましょう
証明
意外と簡単です。
$d(n)$と$\sigma(n)$の値を上から抑えるだけで証明できます。
$d(n)$
$d(n)$というのは$n$の正の約数の個数です。
例えば、$n=24$ならば
正の約数は
\begin{eqnarray}
1&,&24\\
2&,&12\\
3&,&8\\
4&,&6
\end{eqnarray}
の、計8個あります。
$n=36$であれば、
正の約数は
\begin{eqnarray}
1&,&36\\
2&,&18\\
3&,&12\\
4&,&9\\
6
\end{eqnarray}
の計9個あります。
左側の数の個数は
$1,2,...$となって最大でも$\sqrt{n}$なので、
$\sqrt{n}$個以下となります。
それにペアとなって右側にも数があるので、(最後にない場合もありますが、)合計で$2\sqrt{n}$個以下となります。
ピッタリ$2\sqrt{n}$個になることがないことを証明します。
もし、ピッタリ$2\sqrt{n}$個になるとするならば、$n$は平方数でないといけません。
ですが、$n$が平方数だとすると、1番下の数がペアにならずに$\sqrt{n}$のみになってしまいます。これでは$2\sqrt{n}$個を達成することはできません。
よって、正の約数の個数$d(n)$は$2\sqrt{n}$未満です。
すべての自然数$n$に対して
\begin{eqnarray}
d(n) < 2\sqrt{n}
\end{eqnarray}
が成り立つ。
次は$\sigma(n)$です。
$\sigma(n)$
$\sigma(n)$は正の約数の総和なので、
上の2列に並んだやつの和を考えます。
簡単な考え方として、$\frac{n}{2}$以下の正の約数の総和と$\frac{n}{2}$より大きい約数の総和を考えるものがあります。$x$を超えない最大の整数を$[x]$で表すとすると、$\frac{n}{2}$以下の正の約数の総和は$1\sim \frac{n}{2}$までの数の和以下ですから、次のようになります。
\begin{eqnarray}
\qty(\text{$\frac{n}{2}$以下の正の約数の総和}) &\leq&
\sum_{k=1}^{\qty[\frac{n}{2}]}k
\\&=& \frac{1}{2}\qty(\qty[\frac{n}{2}])\qty(\qty[\frac{n}{2}]+1)
\\&=& \frac{1}{2}\qty(\qty[\frac{n}{2}]^2+\qty[\frac{n}{2}])
\\&\leq& \frac{1}{2}\qty(\frac{n^2}{4}+\frac{n}{2})
\\&=& \frac{n^2}{8}+\frac{n}{4}
\end{eqnarray}
また、当たり前ですが$\frac{n}{2}$より大きい約数は$n$しかありませんので、$n$を足して
\begin{eqnarray}
\qty(\text{$n$の正の約数の総和}) &\leq& \frac{n^2}{8}+\frac{5}{4}n
\\
\sigma(n) &\leq& \frac{n^2}{8}+\frac{5}{4}n
\end{eqnarray}
となります。
全ての自然数$n$に対して
\begin{eqnarray}\\
\sigma(n) &\leq& \frac{n^2}{8}+\frac{5}{4}n
\end{eqnarray}が成り立つ。
これにより、$d(\sigma(n))$が上から抑えられることになりました。
それでは問題を証明していきましょう
まず、$n= d(\sigma(n))$となる$n$の必要条件を求めます。$n$は自然数なので$n>0$であることに注意してください。
\begin{eqnarray} 0< n = d(\sigma(n)) &<& 2\sqrt{\frac{n^2}{8}+\frac{5}{4}n} \\ 0 < \frac{n}{2} &<& \sqrt{\frac{n^2}{8}+\frac{5}{4}n} \\ \frac{n^2}{4} &<& \frac{n^2}{8}+\frac{5}{4}n \\ \frac{n^2}{8} - \frac{5}{4}n &<& 0 \\ n\qty(n - 10) &<& 0 \\ \therefore 0< n < 10 \end{eqnarray}
はい、ということです。見事に伏線回収しました。
上の方で事前に行った計算により、すでに$n=1\sim 9$については計算しているので、これで証明は完了したことになります。$Q.E.D.$
もう少し評価を厳しくする
さっき評価した$\sigma(n)$をもう少し厳しく評価します。
先ほどの議論により、左側の数は最大でも$\sqrt{n}$で、$1\sim [\sqrt{n}]$個以下なので
左側の数の和は
\begin{eqnarray} \sum_{k=1}^{[\sqrt{n}]}k&=&\frac{1}{2}([\sqrt{n}])([\sqrt{n}]+1) \\&=&\frac{1}{2}([\sqrt{n}]^2+[\sqrt{n}]) \\&\le&\frac{1}{2}(n+\sqrt{n}) \end{eqnarray}
となりますが、問題は右側です。
\begin{eqnarray} \sum_{k=1}^{[\sqrt{n}]} \frac{n}{k} &=& n\sum_{k=1}^{[\sqrt{n}]} \frac{1}{k} \end{eqnarray}
調和数が出てきましたね。(自然数の逆数和)
これの有名な上からの評価といえば、積分によるものです。
\begin{eqnarray} \sum_{k=1}^{[\sqrt{n}]} \frac{1}{k} &<& 1+\int_1^{[\sqrt{n}]} \frac{1}{x}dx \\&=& 1+ \qty[\ln(x)]_1^{[\sqrt{n}]} \\&\leq& 1+ \qty[\ln(x)]_1^{\sqrt{n}} \\&=&1+\frac{1}{2}\ln(n) \end{eqnarray}
よって、先ほどの式はこう評価できます
\begin{eqnarray} \sum_{k=1}^{[\sqrt{n}]} \frac{n}{k} &=& n\sum_{k=1}^{[\sqrt{n}]} \frac{1}{k} \\&<& n \qty(1+\frac{1}{2}\ln(n)) \\&=& n+ \frac{1}{2}n\ln(n) \end{eqnarray}
それで結局、$\sigma(n)$はこう評価されます。
\begin{eqnarray} \sigma(n) &\le& \qty(\sum_{k=1}^{[\sqrt{n}]}k) + \qty(\sum_{k=1}^{[\sqrt{n}]} \frac{n}{k}) \\&<& \qty(\frac{1}{2}\qty(n+\sqrt{n})) + \qty(n+ \frac{1}{2}n\ln(n)) \\&=& \frac{3}{2}n + \frac{1}{2}\sqrt{n} + \frac{1}{2}n\ln(n) \\&=& \frac{1}{2} \qty(3n+\sqrt{n}+n\ln(n)) \end{eqnarray}
先ほどよりもよりタイトな評価が得られましたね。
全ての自然数$n$に対して
\begin{eqnarray}
\sigma(n) < \frac{1}{2} \qty(n\ln(n)+3n+\sqrt{n})
\end{eqnarray}
が成り立つ。
これはいいですね。なぜならオーダーが$\mathcal{O}(n\ln(n))$だからです。先ほどの評価では$\mathcal{O}(n^2)$でした。
これらの間にある分かりやすい違いは、$k$回反復にあります。
オーダーが$\mathcal{O}(n^2)$の関数を一度反復すると、オーダーが$\mathcal{O}(n^4)$になります。
$k$回反復ならば$\mathcal{O}(n^{2^k})$となってしまいます。
ところが、オーダーが$\mathcal{O}(n\ln(n))$の関数は、一度の反復では
\begin{eqnarray}
\mathcal{O}\qty(n\ln\qty(n)\ln\qty(n\ln\qty(n)))
\end{eqnarray}
つまり、
\begin{eqnarray}
\mathcal{O}\qty(n\qty(\ln\qty(n))^2)
\end{eqnarray}
になりまして、$k$回反復では
\begin{eqnarray}
\mathcal{O}\qty(n\qty(\ln\qty(n))^k)
\end{eqnarray}
となり、常に$\mathcal{O}(n^2)$よりも小さいオーダーになります。
つまり、$\sigma(n)$の$k$回反復である$\sigma^k(n)$は、常に$\mathcal{O}(n^2)$よりも小さいオーダーの関数で上から抑えられます。
このことから次の式が成り立ちます。
任意の自然数$k$に対して、
\begin{eqnarray}
\lim_{n\to \infty} \qty|\frac{\sigma^k(n)}{n^2}| &=& 0
\end{eqnarray}
ランダウの記号の小さいほうの$\mathcal{o}$を使って、
\begin{eqnarray}
\sigma^k(n) = \mathcal{o}(n^2)
\end{eqnarray}
と表せます。
さらに定理1より$d(n)<2\sqrt{n}$ですから、
\begin{eqnarray}
\lim_{n\to \infty} \qty|\frac{d(\sigma^k(n))}{n}|
&<& \lim_{n\to \infty} \qty|\frac{2\sqrt{\sigma^k(n)}}{n}|
\\&=& \lim_{n\to \infty} \qty|{2\sqrt{\frac{\sigma^k(n)}{n^2}}}|
\\&=& 0
\end{eqnarray}
もしくは
\begin{eqnarray}
d(\sigma^k(n)) = \mathcal{o}(n)
\end{eqnarray}
となります。
ここからわかるのは、
任意の自然数$k$に対して
\begin{eqnarray}
d(\sigma^k(n)) = n
\end{eqnarray}
を満たす自然数は高々有限個しかない。
ということです。
