「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.$

$57$ や $91$ は素数ではありませんのでご注意を。このとき、 $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$

が成り立つような $n$ は $n=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_k$ は $k$ 番目の素数までの素数の総和を表す。

$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$ であれば