素数の篩とウラムの螺旋

エラトステネスの篩が合成数を消していく様子を見るか、ウラムの螺旋上の素数を観察しよう。

計算例 — 素数の篩とウラムの螺旋

π(100)	25 個の素数
N / ln N	21.7(13.1% 誤差)
Li(N)	29.1(16.3% 誤差)
双子の組数	8 組
最大ギャップ	8

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — 素数の篩とウラムの螺旋

このパネルは性質の異なる二種類の数を表示しており、ほかを読む前に区別しておく価値があります。π(N) は個数です。ふるいが実際に残した素数の数であり、N = 100 で 25、N = 500 で 95、正確で丸めはありません。その下の二行は、同じ個数の見積もりです。素数定理が主張するのは、片方が極限で比を正しく与えるということであって、数そのものを正しく与えるということではありません。この二つはまったく別の約束であり、その違いが現れる場所が誤差の列です。

各記号の意味

N: ふるいにかける上限であり、唯一の入力。スライダーは 10000 まで。
π(N): N を超えない素数の個数。見積もりではなく数え上げ — ふるいが消さずに残した升目の数そのものです。
N / ln N: その個数の最も単純な見積もり。このスライダーが届くどの N でも、真の値を下回ります。
Li(N): 対数積分 ∫₂ᴺ dt/ln t、より精度の高い見積もり。このスライダーが届くどの N でも、真の値を上回ります。

公式の導き方

ふるいは、ある数が素数かどうかを決して問いません。2 から始めて 2 の倍数をすべて消し、まだ残っている次の数へ進み、その倍数をすべて消し、これを繰り返します。素数性は判定されるのではなく、残ったものがそれなのです。
消す必要があるのは √N 以下の素数の倍数だけです。n ≤ N が合成数なら n = a·b（a ≤ b）と書けるので a ≤ √n ≤ √N — どの合成数も平方根以下の約数を持ち、その約数の番が回ってきた時点ですでに消されています。100 までふるうなら 2、3、5、7 の四回で足ります。
残ったものを数えれば、それがそのまま正確な π(N) です。上の行が事実で、下の二行が意見であるのはこのためです。ふるいは走り終えた副産物として個数を返します。
では比べましょう。素数定理は N が大きくなるとき π(N) · ln N / N → 1 だと述べます。述べていないことに注意してください。比が 1 に近づくことは、百分率の誤差が非常に長いあいだ大きいままであることを許します。次の行が示すのはまさにそれです。

表示の読み方

二つの誤差を競走として読み、N を変えてみてください。N = 100 では粗いほうの見積もりが勝っています。13.1% に対し Li は 16.3%。N = 200 にすると逆転し — 17.9% に対し 6.9% — 二度と戻りません。しかし本当に見るべきは、N/ln N が「しないこと」です。二桁ぶんの範囲で誤差は 14.8%、13.1%、15.3%、13.8%、12.2% と並びます。上下するばかりで、ほとんど改善しません。同じ範囲で Li は 16.3% から 2.8% へ落ちます。どちらの見積もりも素数定理を満たします。目で見える大きさで使えるのは片方だけです。符号も同じくらい一貫していて、ここでは N/ln N がつねに個数より下、Li がつねに上に来ます。

前提: N が丸ごとふるえるほど小さいこと。個数が正確なのは、N までのすべての数を実際に保持して消しているからで、上限が 10¹⁰ ではなく 10000 なのもそのためです。誤差の百分率は π(N) に対して取られているので、測っているのは見積もりであって、個数ではありません。
成り立たない場合: Li(N) > π(N) は、このページが到達できるどの N でも成り立ち、まるで法則のように見えます。法則ではありません。リトルウッドは 1914 年に、この差が符号を無限回変えることを証明しました。つまり Li が下回る N が存在するのです。それから一世紀、誰ひとりその一例すら提示できていません。ベイズとハドソンは 1999 年に最初の交差をおよそ 1.4×10³¹⁶ より下に絞り込み、それ以降さらに狭めた者はいません。つまりこのページは、普遍的でないことが証明済みの模様をあなたに見せており、スライダーをどう動かしても反例には届きません。見えるものと真であることのあいだのこの隔たりこそ、この主題の正直な姿です。

格子の中で見えるこの間引きこそ、誰も証明できていない部分である

素数の正確な分布は、リーマンのゼータ関数 ζ(s) の零点によって支配されています。既知の10¹³個の非自明な零点はすべて、臨界線 Re(s) = 1/2 上にあります。これをすべての零点について証明できれば、素数計数関数に対する最も鋭い評価が得られ、ミレニアム懸賞問題として100万ドルの賞金を獲得できます。2025年時点では未証明です。

調べずにふるい落とす

エラトステネスの篩は、各数を個別に判定するのではなく、消去によって素数を見つけます。2から始めてその倍数をすべて消し、次に残った数へ進んで繰り返すと、一度も消されなかった数が素数です。巧妙なコツは、n までのすべての数をふるうには、√n 以下の素数の倍数だけを消せばよいという点です。だから100未満をふるうには、2、3、5、7の倍数を消すだけで十分です。

退屈から生まれたウラムの落書き

1963年、数学者スタニスワフ・ウラムは講演中の退屈しのぎに整数を正方形の螺旋に書き並べ、素数に印を付けたところ、驚くほど明瞭な対角線の筋が現れました。これらの対角線は、オイラーの n² + n + 41 のような素数の多い二次式に沿っており、この式は n が0から39までのすべてで素数を生みます。なぜ特定の対角線がこれほど密になるのかは、今なお完全には解明されていません。

全プロセスの詳細解説

25 個の素数のふるい落とし（100 未満、手作業） 5 ステップ
100未満の素数は25個存在する。手作業でふるいにかけ（予想以上に少ない労力で済む）、素数定理には小さすぎる標本で素数定理を検証しなさい。
1. ふるいによる計算量の削減こそが、この手法に名前がつけられている理由である。n ≤ 100 が合成数であれば ab と因数分解でき、小さいほうの因数は √100 = 10 を超えられない。したがって、10以下のすべての素数の倍数を消去すればすべての合成数が除外される。つまり、4つの素数で全体の作業が完了する。
  
  $n\le100\ \text{composite}\ \Longrightarrow\ n=ab\ \text{with}\ \min(a,b)\le\sqrt{100}=10$
2. 2、3、5、7の倍数を消去していく。それより小さい数はすでに消去されているため、それぞれ自身の2乗から消し始める。最終的に25個の数が残る。
  
  $\text{strike multiples of }2,3,5,7\ \text{from}\ 4\ \text{upward}\quad\Longrightarrow\quad \pi(100)=25$
3. 素数定理によれば、素数の個数は漸近的に N/ln N となる。N = 100 のとき、この値は 21.7 である。
  
  $\pi(N)\sim\frac{N}{\ln N}:\qquad \frac{100}{\ln 100}=\frac{100}{4.6052}=21.7$
4. この値は13%低く、100という値における漸近的結果としては当然の誤差である。逆の視点から見ても、ここでの有用性は変わらない。N の近くにおける素数の密度は 1/ln N であるため、100付近の数の約22%が素数であるのに対し、100万付近では7.2%となる。素数は対数的に減少するが、これはきわめて緩やかである。
  
  $\frac{25-21.7}{25}=13.1\%,\qquad \frac{1}{\ln 100}=21.7\%\ \ \text{vs}\ \ \frac{1}{\ln 10^{6}}=7.2\%$
5. 素数間隔も整合している。100未満の平均間隔は 100/25 = 4 であり、最大間隔は8（89から97までの区間）である。平均の2倍にとどまり、それ以上悪化することはない。
  
  $\text{mean gap}=\frac{100}{25}=4,\qquad \text{largest}=97-89=8$
解答

ふるいによる結果は π(100) = 25 であり、ツールは推定値を 21.7、13.1%低め と出力する。この誤差は定理の破綻ではなく、定理の収束速度が可視化されたものであり、その収束がきわめて緩やかであることはよく知られている。N を4桁上の 10 000 まで引き上げても、推定値は依然として2桁のパーセントで低めのままである。どのスケールでも成り立つのは密度に関する測定値である。100付近では4.6個に1個、100万付近では13.8個に1個の割合で素数が存在する。対数の増加が非常に緩やかであるため、素数が尽きることはなく、極めて稀になることすら決してない。

$\pi(100)=25\ \text{from four primes};\qquad \frac{N}{\ln N}=21.7\ (13.1\%\ \text{low})$
100未満の8組の双子素数に対する自明な推定 6 ステップ
パネルは 100 未満の素数を 25 個、双子素数を 8 組と数えます。最初の数には 13% まで迫る有名な近似があります。では 2 つ目に対して素直な見積もりを試してみましょう——そして、名前の付いた係数のぶんだけ外れる様子を見てください。
1. 表示された個数と近似を出発点にします。N の近くでは、ある数が素数である確率はおよそ 1/ln N。N = 100 ならおよそ 0.2171 です。
  
  $\pi(100)=25,\qquad \frac{N}{\ln N}=\frac{100}{4.6052}=21.7$
2. 次に n と n+2 が独立だと仮定します。それぞれが確率 1/ln N で素数なら、両方ともである確率はその 2 乗です。
  
  $P_1\approx\frac{1}{\ln N}=0.2171\quad\Longrightarrow\quad P_2\approx P_1^{\,2}=\frac{1}{(\ln N)^{2}}$
3. N を掛けてツールと比べます。見積もりは 100 未満の双子を 4.72 組と言い、ふるいは 8 組を見つけました。少し外れたのではなく、40% 足りません。
  
  $N\,P_2=\frac{100}{21.208}=4.72\qquad\longleftrightarrow\qquad \pi_2(100)=8$
4. 誤りは独立性の仮定で、素数 1 つでその理由が分かります。奇素数 p を取ると、無作為な n は p 個に 1 個の割合で脱落しますが、対は n または n+2 が p で割り切れるたびに脱落します。これは p 個の剰余のうち 2 個。したがって生存率は (p−2)/p であって、独立性が仮定した (p−1)/p の 2 乗ではありません。
  
  $p>2:\quad n\equiv0\ \lor\ n+2\equiv0 \pmod p\quad\Longrightarrow\quad \frac{p-2}{p}\ \neq\ \left(\frac{p-1}{p}\right)^{2}$
5. この補正をすべての奇素数にわたって掛け合わせると、ある定数に収束します。その 2 倍が 1.3203 で、これを当てはめると見積もりは 6.23 に上がります。
  
  $2C_2=2\prod_{p>2}\frac{p(p-2)}{(p-1)^{2}}=1.3203\quad\Longrightarrow\quad 1.3203\times4.72=6.23$
6. N = 100 ではまだ 8 に届きません——この見積もりは漸近的で、100 は小さい数です。収束はします。10⁴ 未満で 156 組、10⁶ 未満で 6917 組。
  
  $N=10^{4}:\ 156\qquad N=10^{6}:\ 6917$
解答

素朴な見積もりは 4.72、補正後は 6.23、そして真の値は 8——補正係数 1.3203 は素数にわたる無限積です。この定数は、独立性のないところに独立性を仮定した代償であり、この分野の難問のほとんどが持つ形をしています。素数はヒューリスティクスが効く程度には無作為で、しかも誰も一から導けない補正を要する程度には構造を持つ。双子素数予想とは、この見積もりの組が尽きることはないという主張であり、いまだ未解決です。

$\pi_2(N)\sim 2C_2\frac{N}{(\ln N)^{2}},\quad 2C_2=1.3203:\qquad 4.72\ \to\ 6.23\ \longleftrightarrow\ 8$

参考文献 (4)

Why the page’s most convincing pattern is not a law — the difference changes sign infinitely often: J. E. Littlewood, "Sur la distribution des nombres premiers." Comptes Rendus de l’Académie des Sciences, Paris 158, 1869–1872, 1914. No DOI: the volume predates them.
How far the first sign change has been pinned down, and where the 1.4×10³¹⁶ comes from: C. Bays & R. H. Hudson, "A new bound for the smallest x with π(x) > li(x)." Mathematics of Computation 69, 1285–1296, 1999.
How far the Riemann hypothesis has actually been verified — note this is a bound on height, a different measure from a count of zeros: D. J. Platt & T. S. Trudgian, "The Riemann hypothesis is true up to 3·10^12." Bulletin of the London Mathematical Society 53, 792–797, 2021.
The prize, and its official problem statement: Clay Mathematics Institute, Millennium Prize Problems — the Riemann Hypothesis.

7 Raven Room チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。