Rokiのチラ裏

学生による学習のログ

Divergence of the sum of the reciprocals of the primes

algorithm C++

素数の逆数和が発散する事(式 (1))についてメモ。
\displaystyle\sum_{p\ prime} \dfrac{1}{p} = \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{5} + \dfrac{1}{7} + \dfrac{1}{11} + \dfrac{1}{13} + \dfrac{1}{17} + \cdots = \infty \tag{1} 素数の逆数和が発散することの証明には Harmonic series*1 が発散する事(式(2))を利用する \displaystyle\lim_{n\to\infty}\sum_{k=1}^n\dfrac{1}{k}= 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \cdots = \infty \tag{2} 式 (2) の証明には、式変形、等式変形による不等式の評価を行う方法と、積分を用いた不等式評価など*2による方法がある。まず式 (2) を証明し、その後式 (1) を証明する。

不等式による (2) の証明

他の発散系列と比較する事で Harmonic series の発散を容易に証明できる。\displaystyle 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dfrac{1}{5} + \dfrac{1}{6} + \dfrac{1}{7} + \dfrac{1}{8} + \dfrac{1}{9} + \cdots \tag{3} \displaystyle 1 + \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{8} + \dfrac{1}{8} + \dfrac{1}{8} + \dfrac{1}{8} + \dfrac{1}{16} + \cdots \tag{4} このとき、\displaystyle 式 (3) \gt 式 (4) である。式 (4) は次の等式 (5) の通り発散する。 (4) = 1 + (\dfrac{1}{2}) + (\dfrac{1}{4} + \dfrac{1}{4}) + (\dfrac{1}{8} + \dfrac{1}{8} + \dfrac{1}{8} + \dfrac{1}{8}) + (\dfrac{1}{16} + \cdots + \dfrac{1}{16}) + \cdots = 1 + \dfrac{1}{2} + \dfrac{1}{2} + \dfrac{1}{2} + \dfrac{1}{2} + \cdots = \infty \tag{5} 現時点で\displaystyle 式 (3) \gt 式 (4)の関係性から明白であるが、さらに、この変形を一般化する事ができ、次の不等式が得られる。 \displaystyle \sum_{n=1}^{2^{k}} \dfrac{1}{n} \geq 1 + \dfrac{k}{2} \tag{6} 式 (6) において k \to \infty とすると、右辺が発散するため左辺も発散する事が言える。 \therefore 題意は示された。

積分による (2) の証明

Integral Test.svg
By Jim.belk - Own work, Public Domain, Link

Harmonic series の総和と広義積分を比較する事で、発散する事を証明できる。各図の面積の和は、 \displaystyle 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dfrac{1}{5} + \cdots + \dfrac{1}{n} と同等である。一方で曲線 y = \dfrac{1}{x} に着目し、 \displaystyle x \in [1, \infty) の部分の下にある面積は \displaystyle \int_{1}^{n + 1}\dfrac{1}{x}dx であり、図から次の不等式が成り立つ。 \displaystyle \int_{1}^{n + 1}\dfrac{1}{x}dx \lt 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dfrac{1}{5} + \cdots + \dfrac{1}{n}
ここで \displaystyle \int_{1}^{n + 1}\dfrac{1}{x}dx = \ln{(n + 1)} であるため、次の不等式が成り立つ。 \displaystyle \ln{(n + 1)} \lt \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dfrac{1}{5} + \cdots + \dfrac{1}{n} < 1 + \ln(n) \tag{7}
式 (7) において n \to \infty とすると、 \displaystyle \lim_{n \to \infty}\ln{(n+1)}=\infty から左辺が発散する事が言え、右辺も発散する事が言える。 \therefore題意は示された。

余談

調和級数 \displaystyle\lim_{n\to\infty}\sum_{k=1}^n\dfrac{1}{k} は見ての通りゼータ関数 \displaystyle \zeta(s)=\displaystyle\sum_{n=1}^{\infty}\dfrac{1}{n^{s}} の \displaystyle \zeta(1) に等しく、ゼータ関数は s \geq 2のときのみ収束する。

(1) の証明

n 以下の素数を昇順に \displaystyle p_{1}, p_{2}, \cdots, p_{t} とすると次の式が成り立つ。 \displaystyle \sum_{k=1}^{p_{n}} \frac{1}{k} \lt\prod_{k=1}^{n}(1+\dfrac{1}{p_{k}}+\dfrac{1}{p_k^{2}}+\dfrac{1}{p_k^{3}}+\cdots) = \prod_{k=1}^{n} \frac{1}{1-\frac{1}{p_{k}}} \tag{8} 式 (8) においては、 \alpha_{1},...,\alpha_{n} を 0 以上の自然数とし、左辺を全て展開すると、 1 以上 p_{n} 以下のいかなる自然数も p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{n}^{\alpha_{n}} と素因数分解できる。また、同式の右辺を展開すると \alpha_{1},...,\alpha_{n} が 0 以上のどのような自然数だとしても必ず \frac{1}{p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{n}^{\alpha_{n}}} となる項がでてくるため、成り立つことが言えるのである。
次に式 (8) の右辺を等比級数の和の公式で変形すると次の式を得る。 \displaystyle\prod_{k=1}^{t}\dfrac{1}{1-\frac{1}{p_{k}}}=\prod_{k=1}^{t}(1+\dfrac{1}{p_{k-1}}) \tag{9} 式 (8) は両辺とも正であるため、次のように不等式の対数を取ることができる。 \ln \left(\displaystyle\sum_{k=1}^{n}\dfrac{1}{k}\right) \lt \displaystyle\ln\left(\prod_{k=1}^{t}(1+\dfrac{1}{p_{k-1}})\right)\ \tag{10}

ln(x+1) と x のグラフ
\ln{(x+1)} と x のグラフ*3
また x \gt 0 のとき、 \ln{(x+1)} \lt x である。これは、 f(x) = x - \ln{(x + 1)}、 f'(x) = 1- \dfrac{1}{x+1}としたとき、 f'(x)=1- \dfrac{1}{x+1}=\dfrac{x}{x+1}\gt0 であり、 f(x) は x\gt0で増加関数となることがいえ、また f(0) = 0 - \ln{1} = 0 であることから、 x\gt0のときf(x)\gt0が導かれる。したがって x\gt0 のとき \ln{(x+1)}\lt xが成り立つ。また \ln{(x+1)} と x のグラフが同様に示す。

この事実から、式 (10) は次のように変形できる。 \displaystyle\sum_{k=1}^{t}\ln(1+\dfrac{1}{p_{k-1}})\ \lt \displaystyle\sum_{k=1}^{t}\dfrac{1}{p_{k-1}} \tag{11} ここで、 \displaystyle p_{k-1}\leq p_{k}-1( k - 1 番目の素数より k 番目の素数は 1 以上大きい)であるから式 (11) を変形し次の式を得る。 1+\displaystyle\sum_{k=2}^{t}\dfrac{1}{p_{k-1}} \leq 1+\displaystyle\sum_{k=2}^{t}\dfrac{1}{p_{k-1}}\ =1+\displaystyle\sum_{k=1}^{t-1}\dfrac{1}{p_{k}}\tag{12} 式 (10)、式 (11) の関係性から、式 (12) は次のように変形できる。 \ln{\left(\displaystyle\sum_{k=1}^{n}\dfrac{1}{k}\right)} \lt 1+\displaystyle\sum_{k=1}^{t(n)-1}\dfrac{1}{p_{k}}\tag{13} ここで n\to\infty とすると式 (2) より左辺が発散するため、右辺も発散する。 \therefore 題意は示された。

総括

最後に素数の逆数和をプロット。

f:id:Rok1:20180219061945p:plain

グラフの通り、発散のスピードが非常に遅いことが窺える。素数列の生成などで篩落とす際は、十分に値が増えたとしてももかなり時間計算量を抑えられるであろうことが視覚的に分かる。プロットで用いた値は、自作ライブラリを利用して次のようにして生成した*4。

#include <srook/math/primes/progression/sieve_atkin.hpp>
#include <srook/math/constants/algorithm/pow.hpp>
#include <srook/math/constants/algorithm/approximate/reciprocal.hpp>
#include <srook/string/to_string.hpp>
#include <fstream>

int main()
{
    constexpr auto max = static_cast<srook::uint32_t>(srook::math::pow(10, 6));
    std::ofstream ofs("data.csv");
    std::size_t i = 0;
    float sum = 0.0;

    srook::math::primes::progression::compute_sieve_atkin_if(max, 
            [&ofs, &i, &sum](srook::uint32_t x) {
                sum += srook::math::approximate::reciprocal(static_cast<float>(x));
                ofs << srook::to_string(i++) + "," + srook::to_string(sum) + "\n";
            },
            [&ofs, &i, &sum](srook::uint32_t) {
                ofs << i++ << "," + srook::to_string(sum) + "\n";
            });
}

グラフは次のように描いた。

#!/usr/local/bin/gnuplot
reset
set object 1 rect behind from screen 0,0 to screen 1,1 fc rgb "#333631" fillstyle solid 1.0
set term png size 800, 600 enhanced
set output 'image.png'
set grid lc rgb "white" lt 2
set border lc rgb "white"
set key tc rgb "white"
set title tc rgb "white"
set xlabel "x" tc rgb "white" font ",30"
set ylabel "y" tc rgb "white" font ",30" offset 1, 0
set size ratio 2.0/(1.0 + sqrt(5.0))
set palette rgbformulae 22, 13, -31
set style line 1 lw 2 lt rgb "#008AD4"

set xrange [0:]
set logscale x
set format x "10^{%L}"
set format y "%3.1f"

set datafile separator ","
set title "The sum of the reciprocals of the primes"
plot "data.csv" using 1:2 w l ls 1

参考

*1:調和級数。音楽の高調波という概念から派生してこのように名付けられている。

*2:英 Wikipedia Harmonic series には "There are several well-known proofs of the divergence of the harmonic series. A few of them are given below." とある通り、これら以外の証明方法がマクローリン型不等式を用いた方法などを含めて、いくつか存在する。

*3:画像は gnuplot で生成した

*4:素数で単に 1 を割れば良いのだが、グラフの様子は大して変わらないので、速度の向上を図るために近似値でプロットしている。言い始めれば、浮動小数点数を使っている時点で近似であるわけだが、106 までの素数の逆数の総和となると図の通り小さい値しか出てこないので、その影響はそこまで酷くもないだろうなどと思いつつ。