約数関数の問題

初めに

始めに、約数関数についての定義をしておきます。

それでは、今回扱う問題について考えていきましょう。

今回の問題

では、実際に1~10についてやってみましょうか
$$\begin{array}{rclrcl}\sigma (1)& =& 1& d(1)& =& 1\\ \sigma (2)& =& 3& d(3)& =& 2\\ \sigma (3)& =& 4& d(4)& =& 3\\ \sigma (4)& =& 7& d(7)& =& 2\\ \sigma (5)& =& 6& d(6)& =& 4\\ \sigma (6)& =& 12& d(12)& =& 6\\ \sigma (7)& =& 8& d(8)& =& 4\\ \sigma (8)& =& 15& d(15)& =& 4\\ \sigma (9)& =& 13& d(13)& =& 2\\ \sigma (10)& =& 18& d(18)& =& 6\end{array}$$
確かに、$n=1\sim 10$では$n=1,2,3,6$のみ成り立っています。
それでは証明していきましょう

証明

意外と簡単です。
$d(n)$と$\sigma (n)$の値を上から抑えるだけで証明できます。

$d(n)$

$d(n)$というのは$n$の正の約数の個数です。
例えば、$n=24$ならば
正の約数は
$$\begin{array}{rcl}1& ,& 24\\ 2& ,& 12\\ 3& ,& 8\\ 4& ,& 6\end{array}$$
の、計8個あります。
$n=36$であれば、
正の約数は
$$\begin{array}{rcl}1& ,& 36\\ 2& ,& 18\\ 3& ,& 12\\ 4& ,& 9\\ 6\end{array}$$
の計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}$未満です。

次は$\sigma (n)$です。

$\sigma (n)$

$\sigma (n)$は正の約数の総和なので、
上の2列に並んだやつの和を考えます。

簡単な考え方として、$\frac{n}{2}$以下の正の約数の総和と$\frac{n}{2}$より大きい約数の総和を考えるものがあります。$x$を超えない最大の整数を$[x]$で表すとすると、$\frac{n}{2}$以下の正の約数の総和は$1\sim \frac{n}{2}$までの数の和以下ですから、次のようになります。

$$\begin{array}{rcl}\left(\frac{n}{2}\text{以下の正の約数の総和}\right)& \le & \sum _{k=1}^{\left[\frac{n}{2}\right]}k\\ & =& \frac{1}{2}\left(\left[\frac{n}{2}\right]\right)(\left[\frac{n}{2}\right]+1)\\ & =& \frac{1}{2}({\left[\frac{n}{2}\right]}^2+\left[\frac{n}{2}\right])\\ & \le & \frac{1}{2}(\frac{n^2}{4}+\frac{n}{2})\\ & =& \frac{n^2}{8}+\frac{n}{4}\end{array}$$
また、当たり前ですが$\frac{n}{2}$より大きい約数は$n$しかありませんので、$n$を足して
$$\begin{array}{rcl}\left(n\text{の正の約数の総和}\right)& \le & \frac{n^2}{8}+\frac{5}{4}n\\ \sigma (n)& \le & \frac{n^2}{8}+\frac{5}{4}n\end{array}$$
となります。

これにより、$d(\sigma (n))$が上から抑えられることになりました。

もう少し評価を厳しくする

これはいいですね。なぜならオーダーが$\mathcal{O}(n\ln \left(n\right))$だからです。先ほどの評価では$\mathcal{O}(n^2)$でした。
これらの間にある分かりやすい違いは、$k$回反復にあります。
オーダーが$\mathcal{O}(n^2)$の関数を一度反復すると、オーダーが$\mathcal{O}(n^4)$になります。
$k$回反復ならば$\mathcal{O}(n^{2^k})$となってしまいます。
ところが、オーダーが$\mathcal{O}(n\ln \left(n\right))$の関数は、一度の反復では
$$\begin{array}{r}\mathcal{O}(n\ln \left(n\right)\ln (n\ln \left(n\right)))\end{array}$$
つまり、
$$\begin{array}{r}\mathcal{O}\left(n{(\ln \left(n\right))}^2\right)\end{array}$$
になりまして、$k$回反復では
$$\begin{array}{r}\mathcal{O}\left(n{(\ln \left(n\right))}^k\right)\end{array}$$
となり、常に$\mathcal{O}(n^2)$よりも小さいオーダーになります。
つまり、$\sigma (n)$の$k$回反復である${\sigma }^k(n)$は、常に$\mathcal{O}(n^2)$よりも小さいオーダーの関数で上から抑えられます。
このことから次の式が成り立ちます。
任意の自然数$k$に対して、
$$\begin{array}{rcl}\underset{n\to \mathrm{\infty }}{lim}\left|\frac{{\sigma }^k(n)}{n^2}\right|& =& 0\end{array}$$
ランダウの記号の小さいほうの$\mathcal{o}$を使って、
$$\begin{array}{r}{\sigma }^k(n)=\mathcal{o}(n^2)\end{array}$$
と表せます。
さらに定理1より$d(n)<2\sqrt{n}$ですから、
$$\begin{array}{rcl}\underset{n\to \mathrm{\infty }}{lim}\left|\frac{d({\sigma }^k(n))}{n}\right|& <& \underset{n\to \mathrm{\infty }}{lim}\left|\frac{2\sqrt{{\sigma }^k(n)}}{n}\right|\\ & =& \underset{n\to \mathrm{\infty }}{lim}\left|2\sqrt{\frac{{\sigma }^k(n)}{n^2}}\right|\\ & =& 0\end{array}$$
もしくは
$$\begin{array}{r}d({\sigma }^k(n))=\mathcal{o}(n)\end{array}$$
となります。
ここからわかるのは、

ということです。