N以下の素数の逆数和の発散速度がlog log Nくらいなことのお気持ち

なんか適当に検索かけても出なかったのでお気持ちだけ書きます。（厳密な証明は英語Wikipediaあたりにあります）

以下、特に断りが無ければ は素数とします。

さて、以下のような事実が知られています。

\begin{align}
\sum_{p} \frac{1}{p} = \infty
\end{align}

素数の逆数和は、調和級数（全ての自然数の逆数和）と同様に発散します。感覚的には、平方数の逆数和は に収束するので、素数は全ての自然数よりは少なくて、でも平方数よりはずっと多いといった感じです。

一方で、上の無限和は発散することには発散するのですが、その速度がめちゃくちゃ遅いことでも有名です。具体的には下のようになります。

\begin{align}
\sum_{p \leq n} \frac{1}{p} = O(\log \log n)
\end{align}

対数のさらに対数ということでかなり遅いことが見て取れます。気になる方は、お手元の電卓か、Wolfram|Alphaで大きい数で計算してみましょう。
ざっくり計算したければ、 という整数の対数 はだいたいその桁数くらいなので、それを2回すると良いです。かなり小さい数字になることが分かると思います。

お役立ち情報

この発散速度が役に立つ場面として、計算機科学における素数判定アルゴリズムの一つである、エラトステネスの篩の（時間）計算量があります。

エラトステネスの篩とは、ある与えられた整数 以下の素数を見つけるためのアルゴリズムです。詳しい話は端折りますが、計算量解析をしてあげると、このアルゴリズムの計算量は 程度になります。愚直に整数を1つずつ まで素数判定をすると になってしまうので、かなりの計算量の改善になっています。

お気持ち

それでは本題です。使う道具は、ゼータ関数のオイラー積表示と関数 のテイラー展開、そして調和級数の発散速度が対数オーダーであることです。

\begin{align}
\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p} \left( 1 - p^{-s} \right)^{-1}
\end{align}

\begin{align}
\log(1+x) = x - \frac{1}{2} x^2 + \frac{1}{3} x^3 - \frac{1}{4} x^4 + \cdots
\end{align}

の対数をとります。

\begin{align}
\log \zeta(1) &= \log \left( \sum_{n=1}^{\infty} \frac{1}{n} \right) \\
&= \log \left( \prod_{p} \left( 1 - \frac{1}{p} \right)^{-1} \right) \\
&= - \sum_{p} \log \left( 1 - \frac{1}{p} \right)
\end{align}

総和の中身の をテイラー級数を使って展開します。

\begin{align}
- \sum_{p} \log \left( 1 - \frac{1}{p} \right) &= - \sum_{p}  \left( - \frac{1}{p} - \frac{1}{2} \cdot \left( \frac{1}{p} \right)^2 - \frac{1}{3} \cdot \left( \frac{1}{p} \right)^3 - \cdots \right) \\
&= \sum_{p}  \left( \frac{1}{p} + \frac{1}{2} \cdot \left( \frac{1}{p} \right)^2 + \frac{1}{3} \cdot \left( \frac{1}{p} \right)^3 + \cdots \right) \\
&= \sum_{p} \frac{1}{p} + \frac{1}{2} \sum_{p} \frac{1}{p^2} + \frac{1}{3} \sum_{p} \frac{1}{p^3} + \cdots
\end{align}

したがって、

\begin{align}
\log \left( \sum_{n=1}^{\infty} \frac{1}{n} \right) = \sum_{p} \frac{1}{p} + \frac{1}{2} \sum_{p} \frac{1}{p^2} + \frac{1}{3} \sum_{p} \frac{1}{p^3} + \cdots
\end{align}

が得られました。

左辺はもう既に完成されてますので、右辺に注目します。

1つ目の項以外は、それぞれ以下のように上から評価できるので、有限値に収束することが分かります。（ は > で絶対収束するため）

\begin{align}
\sum_{p} \frac{1}{p} + \frac{1}{2} \sum_{p} \frac{1}{p^2} + \frac{1}{3} \sum_{p} \frac{1}{p^3} + \cdots \quad \leq \quad \sum_{p} \frac{1}{p} + \frac{1}{2} \zeta(2) + \frac{1}{3} \zeta(3) + \cdots
\end{align}

有限の値は収束発散には影響を及ぼさないので、有限値の部分を全てまとめて とおいてあげると、

\begin{align}
\log \left( \sum_{n=1}^{\infty} \frac{1}{n} \right) = \sum_{p} \frac{1}{p} + S
\end{align}

となります。ざっくり、有限項の和でもこの関係が成り立っていると考えてあげると、以下が得られます。

\begin{align}
\sum_{p \leq N} \frac{1}{p} \quad \approx \quad \log \left( \sum_{n=1}^{N} \frac{1}{n} \right) \quad \approx \quad \log \left( \log N \right)
\end{align}