Divergence of the sum of the reciprocals of the primes
素数の逆数和が発散する事(式 )についてメモ。
素数の逆数和が発散することの証明には Harmonic series*1 が発散する事(式(2))を利用する 式 (2) の証明には、式変形、等式変形による不等式の評価を行う方法と、積分を用いた不等式評価など*2による方法がある。まず式 を証明し、その後式 を証明する。
不等式による (2) の証明
他の発散系列と比較する事で Harmonic series の発散を容易に証明できる。 このとき、 である。式 は次の等式 の通り発散する。 現時点での関係性から明白であるが、さらに、この変形を一般化する事ができ、次の不等式が得られる。 式 において とすると、右辺が発散するため左辺も発散する事が言える。 題意は示された。
積分による (2) の証明
By Jim.belk - Own work, Public Domain, Link
ここで であるため、次の不等式が成り立つ。
式 において とすると、 から左辺が発散する事が言え、右辺も発散する事が言える。題意は示された。
余談
調和級数 は見ての通りゼータ関数 の に等しく、ゼータ関数は のときのみ収束する。
(1) の証明
以下の素数を昇順に とすると次の式が成り立つ。
式 においては、 を 以上の自然数とし、左辺を全て展開すると、 以上 以下のいかなる自然数も と素因数分解できる。また、同式の右辺を展開すると が 以上のどのような自然数だとしても必ず となる項がでてくるため、成り立つことが言えるのである。
次に式 の右辺を等比級数の和の公式で変形すると次の式を得る。
式 は両辺とも正であるため、次のように不等式の対数を取ることができる。
この事実から、式 は次のように変形できる。 ここで、( 番目の素数より 番目の素数は 以上大きい)であるから式 を変形し次の式を得る。 式 、式 の関係性から、式 は次のように変形できる。 ここで とすると式 より左辺が発散するため、右辺も発散する。 題意は示された。
総括
最後に素数の逆数和をプロット。
グラフの通り、発散のスピードが非常に遅いことが窺える。素数列の生成などで篩落とす際は、十分に値が増えたとしてももかなり時間計算量を抑えられるであろうことが視覚的に分かる。プロットで用いた値は、自作ライブラリを利用して次のようにして生成した*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." とある通り、これら以外の証明方法がマクローリン型不等式を用いた方法などを含めて、いくつか存在する。
*4:素数で単に 1 を割れば良いのだが、グラフの様子は大して変わらないので、速度の向上を図るために近似値でプロットしている。言い始めれば、浮動小数点数を使っている時点で近似であるわけだが、106 までの素数の逆数の総和となると図の通り小さい値しか出てこないので、その影響はそこまで酷くもないだろうなどと思いつつ。