インテジャーズ

インテジャーズ

数、特に整数に関する記事。

「n以下の素数の個数」以下の素数の和がnに等しくなるような最大の自然数は100である

本日の数遊び

100 以下の素数は25個あります:


\displaystyle 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.


5791は素数ではありませんのでご注意を。このとき、25という数に着目して、25以下の素数を足し合わせると


2+3+5+7+11+13+17+19+23=100


となっています。


実は、100はこのような性質を持つ最大の自然数なのです。本日は次の定理を証明することにいたしましょう。

実数xに対して、\pi(x)x以下の素数の個数、S(x)x以下の素数の総和とします。


定理 nを正の整数とする。このとき、

\displaystyle S(\pi(n))=n

が成り立つような nn=5, 17, 41, 77, 100 に限る。

定理の証明(の一例)

以前示したように

\displaystyle S(x) \sim \frac{x^2}{2\log x}

なので、素数定理より S(\pi(n))=n が十分大きいnに対して成立しないことは即座にわかる。ただし、定理を証明するにはeffectiveな評価をする必要があるため、以下にその一例を示す。

素数定理のeffective版として、次の定理を利用する(証明は当ブログでは残念ながら紹介できない)。

Rosser-Schoenfeldの定理(の一つ) \ x \geq 17であれば
\displaystyle \pi(x) > \frac{x}{\log x}
が成り立ち、x > 1であれば
\displaystyle \pi(x) < \frac{1.25506x}{\log x}
が成り立つ。

しばらくは、x \geq 100とする*1。以前も紹介したように

\displaystyle S(x) = -\sum_{2 \leq n \leq x}\pi(n)+\pi(x) \left( [x]+1\right)

が成り立つので、Rosser-Schoenfeldより

\displaystyle S(x) > -1.26\sum_{n \leq x}\frac{n}{\log n} + \frac{x^2}{\log x}

と評価できる。2以上x以下の整数の和は \frac{[x]([x]+1)}{2}-1 であるが、x \geq 48に対して

\displaystyle \frac{[x]([x]+1)}{2}-1 \leq \frac{x^2+x-2}{2} < 0.51x^2

が成り立つ。これに注意して、アーベルの総和法を適用すると

\displaystyle \sum_{2 \leq n \leq x}\frac{n}{\log n} < \frac{0.51x^2}{\log x}+0.51\int_2^x\frac{t}{\log^2t}dt

を得る。ここで更に、例えば

\begin{align} \int_2^x\frac{t}{\log^2t}dt &< \frac{0.68x^2}{\log^2x} \quad (x \geq 100) \\ \frac{x^2}{\log^2x} &< \frac{0.22x^2}{\log x} \quad (x \geq 95) \end{align}

が成り立つことに注意すると、

\displaystyle  \sum_{2 \leq n \leq x}\frac{n}{\log n} < \frac{0.59x^2}{\log x}

となり、

\displaystyle S(x) > \frac{x^2}{4\log x} \quad (x \geq 100) −①

が証明された。すると、x \geq 541であれば*2

\displaystyle S(\pi(x)) > \frac{\pi(x)^2}{4\log \pi(x)} > \frac{x^2}{4\log^3x}

と下から押さえることができるが、

\displaystyle \frac{x^2}{4\log^3x} > x \quad (x \geq 1611)

なので、S(\pi (n)) = nが成り立つならば n \leq 1610でなければならないことが示された。

後は以下の表を見れば定理の証明が完了する。ただし、S_kk番目の素数までの素数の総和を表す。

S_n \pi(S_n) \pi \left(\pi(S_n)\right)
S_1=2 1 0
S_{\color{red}{2}}=5 3 \color{red}{2}
S_{3}=10 4 2
S_{\color{red}{4}}=17 7 \color{red}{4}
S_{5}=28 9 4
S_{\color{red}{6}}=41 13 \color{red}{6}
S_{7}=58 16 6
S_{\color{red}{8}}=77 21 \color{red}{8}
S_{\color{red}{9}}=100 25 \color{red}{9}
S_{10}=129 31 11
S_{11}=160 37 12
S_{12}=197 45 14
S_{13}=238 51 15
S_{14}=281 60 17
S_{15}=328 66 18
S_{16}=381 75 21
S_{17}=440 85 23
S_{18}=501 95 24
S_{19}=568 103 27
S_{20}=639 115 30
S_{21}=712 127 31
S_{22}=791 138 33
S_{23}=874 150 35
S_{24}=963 162 37
S_{25}=1060 177 40
S_{26}=1161 191 43
S_{27}=1264 205 46
S_{28}=1371 219 47
S_{29}=1480 233 51
S_{30}=1593 250 53

Q.E.D.

追記

記事を書いた後に調べてみたところ、この問題はGolombによって雑誌Amer. Math. Month. に提出されており、1991年にMarcin E. Kuczmaという人の解答が掲載されていました。私はある程度精密な①を示してS_kについてはS_{30}以下を調べる形にまとめましたが、Marcin E. Kuczma氏の解答はS_kについてのより自明な評価しか用いていないにも関わらずS_{22}以下を調べればよいという形にまとまっています(Rosser-Schoenfeldを使うのは同じ)。以下にその解答を記述します。

Marcin E. Kuczmaによる証明. 問題は \pi\left(\pi(S_k)\right)=k なるkを求めることと同値である。k番目の素数を p_kとすると明らかに p_k \geq 2k-1なので、帰納法によって S_k > k^2 がわかる。Rosser-Schoenfeldの定理*3のうち、

\displaystyle \pi(x) > \frac{x}{\log x - \frac{1}{2}} \quad (x \geq 67)

を使うと、

\displaystyle \frac{\log (\log n-\frac{1}{2})}{\log n} < 1-\frac{1}{\sqrt{2}} \quad (n \geq 241)

と数値計算を合わせて、n \geq 149であれば \pi(n) > n^{\frac{1}{\sqrt{2}}} が成り立つことがわかる。よって、n \geq 859であれば*4 \pi\left(\pi(n)\right) > n^{\frac{1}{2}}が成り立つ。S_{23}=874 > 859なので、k \geq 23であれば

\displaystyle \pi\left(\pi(S_k)\right) > S_k^{\frac{1}{2}} > k

が示された。よって、後はk \leq 22について表を確認すればよい。 Q.E.D.

*1:特に意味はない。

*2:\pi(541)=100.

*3:これは同一論文内に大量の定理があります。

*4:\pi(859)=149.