Working notes on the primes
Grant Golland’s working notes on how the prime numbers are spread out. Every figure is computed here from a sieve of all 5 761 455 primes below 100 000 000, or with mpmath, and its caption says how. A sibling site, Zeta Zeros, covers the zeros that control these patterns.
Sentences carry a flag: Settled for proved theorems or computations on a stated range, Open for conjectures. A numerical match is never a proof.
Step 2
How many primes: the Prime Number Theorem
Write π(x) for the number of primes up to x. Near a large number x, about one number in log x is prime (natural logarithm). Adding that density up gives Gauss’s guess Li(x), and it is astonishingly good.
At this scale the counted staircase and Li(x) are almost one curve. The simpler x/log x has the right shape but runs about 10 percent low.
| x | π(x), counted | Li(x), rounded | x/log x | π(x)/Li(x) |
|---|---|---|---|---|
| 10 | 4 | 5 | 4 | 0.80000 |
| 100 | 25 | 29 | 22 | 0.86207 |
| 1 000 | 168 | 177 | 145 | 0.94915 |
| 10 000 | 1 229 | 1 245 | 1 086 | 0.98715 |
| 105 | 9 592 | 9 629 | 8 686 | 0.99616 |
| 106 | 78 498 | 78 627 | 72 382 | 0.99836 |
| 107 | 664 579 | 664 917 | 620 421 | 0.99949 |
| 108 | 5 761 455 | 5 762 208 | 5 428 681 | 0.99987 |
The theorem
- Settled The Prime Number Theorem: π(x) divided by x/log x tends to 1. Proved independently by Jacques Hadamard and Charles de la Vallée Poussin in 1896, both by showing that ζ(s) has no zeros on the line Re s = 1.
- Settled Gauss (letter to Encke, 1849, recalling work from about 1792) and Legendre (1798, 1808) conjectured it from tables. Riemann’s 1859 memoir showed how the zeros of ζ control the error.
- Settled de la Vallée Poussin (1899) proved the error π(x) − Li(x) is smaller than x·exp(−c√log x) for some constant c. Elementary proofs, without complex analysis, were found by Selberg and Erdős in 1949.
- Open The Riemann Hypothesis is equivalent to the sharper error bound |π(x) − Li(x)| ≤ C√x log x (von Koch, 1901). It is unproved. See the Zeta Zeros site.
- Settled Li(x) is larger than π(x) for every x in this table, but not forever: Littlewood (1914) proved the sign changes infinitely often. The first crossing is known only to lie below about 1.4 × 10316 (Bays and Hudson 2000; later refinements); none has been seen in any computed table.
Reading path · step 3 of 11