素数計数関数

同義語：prime-counting function

概要

前提知識: 素数, 床関数, 素数の無限性

$10$ 以下の素数は $2,3,5,7$ の $4$ 個、$100$ 以下では $25$ 個、$1000$ 以下では $168$ 個、$100$ 万以下では $78498$ 個ある。$x$ 以下の素数の個数を $\pi(x)$ と書くと、$\pi(10)=4$、$\pi(100)=25$、$\pi(1000)=168$、$\pi(10^6)=78498$ である。素数は無限にある（素数の無限性）ので $\pi(x)$ はいくらでも大きくなるが、割合 $\pi(x)/x$ は $0.4$、$0.25$、$0.168$、$0.0785$ と小さくなっていく。逆数 $x/\pi(x)$ は $x=10,10^2,\dots,10^6$ で $2.5$、$4.0$、$5.95$、$8.14$、$10.43$、$12.74$ となり、$x$ が大きくなると、$10$ 倍になるごとにほぼ $2.3$ ずつ増える（$10^4$ から $10^5$ で $2.29$、$10^5$ から $10^6$ で $2.31$）。$\log10=2.302\ldots$ なので、これは $\pi(x)$ がおよそ $x/\log x$ であることを示唆する。実際 $x/\log x$ は $x=10,100,1000,10^6$ で $4.3$、$21.7$、$144.8$、$72382$ である。
この関数 $\pi$ を 素数計数関数 という。本記事では $\pi(x)$ の定義と値の表、値を求める Eratosthenes の篩と篩から得られる $\pi(x)$ の公式、$\pi(x)$ の下からの評価、素数の割合 $\pi(x)/x$ が $0$ に近づくことを証明し、素数定理 $\pi(x)\sim x/\log x$ などの深い結果との関係を述べる。記号 $\pi$ は円周率とは関係がない。

定義

$x$ 以下の素数を数える関数

実数 $x$ に対し、$x$ 以下の素数の個数を
$$ \pi(x):=\#\{p\mid p\ \text{は素数},\ p\le x\} $$
と書き、関数 $\pi$ を 素数計数関数（prime-counting function）という。

$x<2$ なら $\pi(x)=0$ である。$\pi(x)$ は $x$ について単調に増加し、値は素数のところでちょうど $1$ ずつ増え、それ以外では一定である（階段関数）。$\pi(x)=\pi(\lfloor x\rfloor)$ であり（$\lfloor\cdot\rfloor$ は床関数）、たとえば $\pi(7.5)=\pi(7)=4$ である。小さい順に $n$ 番目の素数を $p_n$ と書くと（$p_1=2$、$p_2=3$、…）、$\pi(p_n)=n$ であり、$\pi$ は素数の列の「逆関数」の役をする。同じ関数は素数定理の記事の定義「素数計数関数と漸近同値」でも定義されている（Cri24 Definition 21.0.1、p. 367。Sho08 §5.1、p. 104。Ste17 §1.2.5、p. 15）。

直感

素数は小さい数の間では密に、大きい数の間ではまばらに現れる。$\pi(x)$ はその「累計」を表し、$\pi(x)/x$ は $x$ 以下の数のうち素数である割合である。$x$ 付近の数が素数である「確率」がおよそ $1/\log x$ だと考えると、それを足し合わせた $\pi(x)$ は $x/\log x$ や $\int_2^x dt/\log t$ に近いはずだ、というのが Gauss の見通しであり、これは素数定理として証明された。一方、$\pi(x)$ の値を正確に知るには素数を 1 つずつ確かめる必要はなく、篩の考え方を使えば、小さい素数だけの情報から包除原理で数えられる（thm-pcf-sieve-formula）。

例と反例

値の表

$\operatorname{Li}(x):=\int_2^x\frac{dt}{\log t}$（対数積分）とおく。$\pi(x)$ と $x/\log x$、$\operatorname{Li}(x)$ の値は次のとおりである（$x/\log x$ と $\operatorname{Li}(x)$ は小数第 1 位で四捨五入）。

$x$	$\pi(x)$	$x/\log x$	$\operatorname{Li}(x)$
$10$	$4$	$4.3$	$5.1$
$10^2$	$25$	$21.7$	$29.1$
$10^3$	$168$	$144.8$	$176.6$
$10^4$	$1229$	$1085.7$	$1245.1$
$10^5$	$9592$	$8685.9$	$9628.8$
$10^6$	$78498$	$72382.4$	$78626.5$
$10^9$	$50847534$	$48254942.4$	$50849233.9$

比 $\pi(x)/(x/\log x)$ は $x=10^3$ で約 $1.161$、$10^6$ で約 $1.084$、$10^9$ で約 $1.054$ と、$1$ に向かってゆっくり近づく。$\operatorname{Li}(x)$ のほうが $\pi(x)$ にずっと近い（$\pi(10^6)$ と $\pi(10^9)$ の値は Sho08 Table 5.1、p. 105 と一致する）。

反例：素数の割合は単調に減るとは限らない

$\pi(6)/6=3/6=0.5$ だが $\pi(7)/7=4/7=0.571\ldots$ である。一般に素数 $p$ のところで割合 $\pi(x)/x$ は跳ね上がる。$\pi(x)/x$ は「$x\to\infty$ で $0$ に収束する」（prop-pcf-density-zero）ことを満たすが、「$x$ について単調に減少する」ことを満たさない。「$0$ に収束する関数は単調に減少する」という含意が $\pi(x)/x$ で破れる。

反例：計算できる範囲の不等式 $\pi(x)<\operatorname{Li}(x)$ はすべての $x$ では成り立たない

ex-pcf-table のどの $x$ でも $\pi(x)<\operatorname{Li}(x)$ であり、$8\le x\le2\cdot10^5$ のすべての $x$ でもこの不等式が成り立つ（$x=7$ では $\pi(7)=4>\operatorname{Li}(7)=3.71\ldots$）。計算機で調べられた範囲では逆転は見つかっていない。しかし Littlewood は、どんなに大きな $x$ に対しても $\operatorname{Li}(x')<\pi(x')$ となる $x'>x$ が存在することを証明した（Cri24 Fact 21.2.6 と Historical remark 21.2.7、p. 374。本記事では証明しない）。最初にそうなる $x'$ はきわめて大きく、Skewes による上界以来その位置の上界が改良されてきたが、具体的な値は知られていない（同所）。$\pi$ と $\operatorname{Li}$ は「計算できる範囲の $x\ge8$ で $\pi(x)<\operatorname{Li}(x)$」を満たすが、「すべての $x\ge8$ で $\pi(x)<\operatorname{Li}(x)$」を満たさない。有限個の数値の確認から一般の不等式を結論する推論が、ここで破れる。

性質

Eratosthenes の篩

$N$ 以下の素数をすべて求め、$\pi(N)$ を数える最も古い方法が Eratosthenes の篩（Eratosthenesの篩）である。$2$ から $N$ までの整数を書き並べ、$d=2,3,\dots,\lfloor\sqrt N\rfloor$ の順に、その時点で $d$ が消されていなければ、$d$ の $2$ 倍以上の倍数 $2d,3d,\dots$（$N$ 以下）をすべて消す。

篩の正しさ

$N\ge2$ を整数とする。上の手順を終えたとき消されずに残っている数は、ちょうど $N$ 以下の素数である。また、手順の途中で $d$ の番が来たとき $d$ が消されていないことと、$d$ が素数であることは同値である。

合成数には小さい素因数がある

まず後半を $d$ についての帰納法で示す。$d$ の番の時点で $d$ が消されていることは、$d$ より小さいある $d'$（その番に消されていなかった数、帰納法の仮定により素数）について $d$ が $d'$ の $2$ 倍以上の倍数であることと同値である。$d$ が合成数なら、素数の記事の命題「素因数の存在」の 2 により $\sqrt d$ 以下の素因数 $q$ をもち、$q< d$ で $d$ は $q$ の $2$ 倍以上の倍数なので、$q$ の番に消されている。$d$ が素数なら、$d$ より小さい $2$ 以上の数の $2$ 倍以上の倍数にはならないので消されていない。
前半：手順で消される数は、ある素数 $p\le\sqrt N$ の $2$ 倍以上の倍数、つまり $p$ で割り切れて $p$ と異なる数であり、合成数である。したがって素数は消されない。逆に $N$ 以下の合成数 $k$ は、同じ命題により $\sqrt k\le\sqrt N$ 以下の素因数 $q$ をもち、$k\ne q$ なので、$q$ の番（$q\le\lfloor\sqrt N\rfloor$）に消される。よって残る数はちょうど素数である。$\square$

たとえば $N=30$ では $\lfloor\sqrt{30}\rfloor=5$ なので、$2,3,5$ の倍数を消すだけで、残る $2,3,5,7,11,13,17,19,23,29$ が $30$ 以下の素数のすべてであり、$\pi(30)=10$ である（$4$ の番では $4$ はすでに消されている）。篩の手順と正しさは Sho08 §5.4（p. 115。証明の詳細は演習）、Cri24 Algorithm 6.2.3（p. 76）、Ste17 §1.2.2 の Algorithm 1.2.3（p. 12）にある。同じ原理で $1$ つの数を素因数分解する方法は素因数分解の記事の命題「試し割りの正しさ」にある。

篩による $\pi(x)$ の公式

篩で消されずに残る数を、素数を 1 つずつ調べずに数えることができる。

篩による $\pi(x)$ の公式

$x\ge1$ を実数とし、$\sqrt x$ 以下の素数全体の積を $P$ とする（$\sqrt x<2$ なら $P=1$）。このとき
$$ \pi(x)-\pi(\sqrt x)+1=\sum_{d\mid P}\mu(d)\left\lfloor\frac xd\right\rfloor $$
が成り立つ。和は $P$ の正の約数 $d$ 全体にわたり、$\mu$ は Möbius関数である。

$P$ と互いに素な数を数える

$N:=\lfloor x\rfloor$ とおく。Möbius関数の記事の命題「互いに素な数の個数」により、$1\le k\le N$ で $\gcd(k,P)=1$ となる $k$ の個数は $\sum_{d\mid P}\mu(d)\lfloor N/d\rfloor$ であり、床関数の記事の命題「入れ子の床関数」により $\lfloor N/d\rfloor=\lfloor x/d\rfloor$ である。したがって、$1\le k\le x$ で $P$ と互いに素な整数 $k$ の個数が $\pi(x)-\pi(\sqrt x)+1$ であることを示せばよい。
$k=1$ は $P$ と互いに素である。$2\le k\le x$ のとき、$k$ が $P$ と互いに素であることは、$k$ が $\sqrt x$ 以下のどの素数でも割り切れないことと同値である。$k$ が素数なら、これは $k>\sqrt x$ と同値である。$k$ が合成数なら、素数の記事の命題「素因数の存在」の 2 により $\sqrt k\le\sqrt x$ 以下の素因数をもつので、$P$ と互いに素にならない。よって数えている $k$ は、$1$ と、$\sqrt x< p\le x$ を満たす素数 $p$ であり、その個数は $1+\pi(x)-\pi(\sqrt x)$ である。$\square$

$x=100$ では $\sqrt{100}=10$ 以下の素数は $2,3,5,7$、$P=210$ で、$d$ を素因数の個数で分けると
$$ 100-(50+33+20+14)+(16+10+7+6+4+2)-(3+2+1+0)+0=100-117+45-6=22 $$
となる。左辺は $\pi(100)-\pi(10)+1=25-4+1=22$ であり、$\pi(10)=4$ から $\pi(100)=25$ が求まる。一般に $\pi(\sqrt x)$ が分かっていれば $\pi(x)$ が求まり、$\pi(\sqrt x)$ も同じ公式で $\pi(x^{1/4})$ から求まる。和の項の数は $2^{\pi(\sqrt x)}$ あるので大きな $x$ ではこのままでは使えないが、項をまとめて計算量を減らす工夫をした方法が、実際に $\pi(x)$ を計算するのに使われている（Cri24 §21.1.3、p. 370 は同じ公式を「$\sqrt n$ 以下の素数で割り切れない数の個数」の関数を使って $\pi(n)=\pi(\sqrt n)+\phi(n,\pi(\sqrt n))-1$ と書き、この形が計算に使われると述べている）。包除原理の形では包除原理の記事の命題「素数で割り切れない数の個数」にあたる。

下からの評価

素数が無限にあることは $\pi(x)\to\infty$ を意味する。どのくらいの速さで大きくなるかについて、素因数分解だけを使って次の評価が得られる。

対数による下からの評価

すべての正の整数 $N$ について
$$ \pi(N)\ge\frac12\log_2N $$
である。

平方因子をもたない部分と平方の部分に分ける

$k:=\pi(N)$ とし、$N$ 以下の素数を $p_1,\dots,p_k$ とする。素因数分解の記事の命題「平方因子をもたない部分と平方の部分への分解」により、$1\le n\le N$ を満たす整数 $n$ は、平方因子をもたない正の整数 $s$ と正の整数 $m$ によって $n=sm^2$ とただ 1 通りに書ける。$s$ は相異なる素数の積（または $1$）で、その素因数は $n\le N$ を割り切るので $p_1,\dots,p_k$ のどれかである。したがって $s$ は $\{p_1,\dots,p_k\}$ の部分集合で決まり、$s$ の候補は高々 $2^k$ 個である。また $m^2\le n\le N$ なので $m\le\sqrt N$ であり、$m$ の候補は高々 $\sqrt N$ 個である。$n\mapsto(s,m)$ は単射なので
$$ N\le2^k\sqrt N $$
であり、$2^k\ge\sqrt N$、すなわち $k\ge\frac12\log_2N$ である。$\square$

$N=10^6$ ではこの評価は $\pi(10^6)\ge9.96\ldots$ にすぎず、実際の $78498$ よりはるかに小さい。それでも、素数の無限性の記事の命題「素数の大きさの二重指数の上界」から得られる $\pi(x)>\log_2\log_2x$（$x\ge2$）と比べると、$N\ge16$ では $\frac12\log_2N\ge\log_2\log_2N$（$N=16$ で等号、$N>16$ で真に大きい）であり、$N$ が大きくなるとその差は非常に大きくなる（比 $\dfrac{\frac12\log_2N}{\log_2\log_2N}$ は $N\to\infty$ で発散する）。$\pi(x)$ の本当の大きさは、Chebyshev が示した
$$ \frac{\log2}{4}\cdot\frac{x}{\log x}\le\pi(x)<7\cdot\frac{x}{\log x}\qquad(x\ge2) $$
の程度である（素数定理の記事の定理「Chebyshevの評価」。定数は同記事のもの）。また Bertrandの仮説の記事の定理「Bertrand–Chebyshevの定理」は、すべての正の整数 $n$ について $\pi(2n)-\pi(n)\ge1$ であることを言っている。

素数の割合は 0 に近づく

素数の割合の極限

$$ \lim_{x\to\infty}\frac{\pi(x)}{x}=0 $$
である。

小さい素数で篩ってから数える

正の整数 $r$ を固定し、最初の $r$ 個の素数 $p_1,\dots,p_r$ の積を $Q$ とする。$x$ 以下の素数は、$p_1,\dots,p_r$ のどれかであるか、$Q$ と互いに素な整数である。
連続する $Q$ 個の整数 $a+1,\dots,a+Q$ は $Q$ で割った余りがすべて異なり、$\gcd(k,Q)$ は $k$ を $Q$ で割った余りだけで決まるので、その中で $Q$ と互いに素なものの個数は $1,\dots,Q$ の中の個数 $\varphi(Q)$ に等しい（Eulerのφ関数）。$1$ から $\lfloor x\rfloor$ までの整数は、このような長さ $Q$ の区間 $\lfloor x/Q\rfloor+1$ 個で覆えるので、$x$ 以下で $Q$ と互いに素な正の整数は $\bigl(x/Q+1\bigr)\varphi(Q)$ 個以下である。Eulerのφ関数の記事の定理「素因数分解による公式」により $\varphi(Q)=Q\prod_{i=1}^r(1-1/p_i)$ なので、
$$ \pi(x)\le r+x\prod_{i=1}^r\Bigl(1-\frac1{p_i}\Bigr)+Q $$
である（$\varphi(Q)\le Q$ を使った）。両辺を $x$ で割って $x\to\infty$ とすると、$r$ と $Q$ は固定されているので
$$ \limsup_{x\to\infty}\frac{\pi(x)}{x}\le\prod_{i=1}^r\Bigl(1-\frac1{p_i}\Bigr) $$
を得る。素数の無限性の記事の命題「Euler積の下からの評価」により、$y\ge2$ について $\prod_{p\le y}(1-1/p)^{-1}>\log y$、すなわち $\prod_{p\le y}(1-1/p)<1/\log y$ である。$y=p_r$ とすると右辺の積は $1/\log p_r$ より小さく、$r\to\infty$ で $p_r\to\infty$ なので $0$ に近づく。$\pi(x)/x\ge0$ なので極限は $0$ である。$\square$

$r=4$（$p_1,\dots,p_4=2,3,5,7$、$Q=210$）なら $\prod(1-1/p_i)=48/210=0.228\ldots$ で、「$\pi(x)$ は十分大きな $x$ で $x$ の約 $23$ パーセントを超えない」ことが分かる。$x=10^6$ での実際の割合は $0.0785$ である。この事実は素数定理からも直ちに従う（Ste17 §1.2.5、p. 15）が、上の証明は素数定理を使わない。

素数定理

素数定理の主張

$$ \lim_{x\to\infty}\frac{\pi(x)}{x/\log x}=1 $$
である。すなわち $\pi(x)\sim x/\log x$ であり、$\pi(x)\sim\operatorname{Li}(x)$ とも書ける。

素数定理の証明の所在

これは素数定理の記事の定理「素数定理」であり、本記事では証明しない。1896 年に Hadamard と de la Vallée Poussin が独立に証明した。証明の出典と歴史、$\operatorname{Li}(x)$ による形と誤差項、Riemann予想との関係は同記事の注意「証明の出典と歴史」「対数積分による形と誤差項」にある。$\pi(x)\sim x/\log x$ は比についての主張であり、差 $\pi(x)-x/\log x$ は $x\to\infty$ で大きくなっていく（同記事の例「反例：漸近同値でも差は大きくなる」）。$n$ 番目の素数については $p_n\sim n\log n$ が従う（同記事の系「n番目の素数の大きさ」）。

補足

歴史と文献

Legendre と Gauss は 1800 年前後に素数の表を作って $\pi(x)$ を調べ、Legendre は $x/(\log x-A)$（$A\approx1.08366$）の形の近似を、Gauss は $\int_2^x dt/\log t$ による近似を考えた（Cri24 §21.2、pp. 371–373）。Gauss は 1849 年の手紙で $300$ 万以下の素数を $216745$ 個と書いているが、正しくは $216816$ 個である（Ste17 §1.2.5、p. 15）。$\pi(x)$ の値の表は Ste17 Table 1.1（p. 16）、Sho08 Table 5.1（p. 105）にある。$\pi(x)$ の値を階乗を使って正確に表す式もあるが、実際の計算には役に立たない（Cri24 §21.1.1、p. 368）。