The idea: count the primes up to x
Write π(x) for the number of primes that are at most x. π(10) = 4 (2, 3, 5, 7), π(30) = 10 and π(100) = 25. As a graph π(x) is a staircase: flat between two primes, one step up at each prime. The steps get further apart as x grows: the primes thin out. The question is how fast.
The canvas draws the staircase in blue against the smooth guess x / ln x in orange, and below it one dot per prime p at the height of the gap to the next prime. Demo: the first ten primes, one by one walks from 2 to 29; Demo: sweep to 100 draws the whole staircase up to 100.
Thinning out: one number in ln x
Among the numbers near x, roughly 1 in ln x is prime, where ln is the natural logarithm. ln x grows very slowly, so the primes thin out very slowly too. Near 100 about 1 number in 4.6 is prime, near a million still 1 in 13.8. Every time x is multiplied by 10, the chance drops only by adding ln 10 ≈ 2.3 to the "1 in …".
| x | π(x) | x / ln x | π(x) ÷ (x / ln x) | li(x) | li(x) − π(x) | x / π(x) |
|---|---|---|---|---|---|---|
| 100 | 25 | 21.7 | 1.151 | 30.1 | 5.1 | 4.00 |
| 1000 | 168 | 144.8 | 1.161 | 177.6 | 9.6 | 5.95 |
| 10 000 | 1229 | 1085.7 | 1.132 | 1246.1 | 17.1 | 8.14 |
| 100 000 | 9592 | 8685.9 | 1.104 | 9629.8 | 37.8 | 10.43 |
| 1 000 000 | 78 498 | 72 382.4 | 1.084 | 78 627.5 | 129.5 | 12.74 |
The last column is the average gap between primes up to x. It grows like ln x − 1 (3.6, 5.9, 8.2, 10.5, 12.8). Demo: zoom out 100 → 10 000 sweeps three ranges in turn: from far away the steps of 1 shrink and the staircase looks like a smooth curve.
The prime number theorem
Legendre and the 15-year-old Gauss guessed it from prime tables around 1792–1798; Hadamard and de la Vallée Poussin proved it in 1896. The prime number theorem says
π(x) ÷ (x / ln x) → 1 as x → ∞It does not say that π(x) and x / ln x are close. The difference keeps growing (6000 at a million); only the ratio goes to 1, and it goes very slowly: 1.16 at 1000, 1.08 at a million, still 1.02 at 10²⁰. For every x ≥ 17 the staircase is above x / ln x.
li(x) is a much better guess
If a number t is prime with chance 1 / ln t, then the expected number of primes up to x is the sum of those chances, which is the area under 1 / ln t: the logarithmic integral
li(x) = ∫₀ˣ dt / ln t li(1000) ≈ 177.6, li(10⁶) ≈ 78 627.5x / ln x uses the chance at the top end, 1 / ln x, for every number below x, which is too small; li(x) uses the right chance for each t. So li(x) is off by only 130 at a million where x / ln x is off by 6116 (Demo: up to a million, which turns on both curves; the curve menu under Options does the same). An integral is an area that grows with x: see the Fundamental Theorem of Calculus.
li(x) is above π(x) for every x anyone has computed, yet Littlewood proved in 1914 that the two cross infinitely often; the first crossing is somewhere below 10³¹⁷. How small the error li(x) − π(x) stays is exactly the Riemann hypothesis: about √x · ln x if it is true.
Gaps between primes
The gap after a prime p is the distance to the next prime. Since 1 number in ln p is prime, the gaps average about ln p (the dashed purple curve in the gap chart). Single gaps scatter widely around it:
- Twin primes such as 11, 13 or 9929, 9931 have the smallest possible gap, 2. They keep appearing along the bottom row of dots; whether there are infinitely many is the twin prime conjecture (Zhang proved in 2013 that some gap below 70 million repeats for ever, now lowered to 246).
- Record gaps are longer than every gap before them (red dots): 8 after 89, 14 after 113, 34 after 1327, 36 after 9551, 72 after 31 397, 114 after 492 113. They grow, but in every case checked they stay below (ln p)² (Cramér's conjecture).
- Gaps can be as long as you like: n! + 2, n! + 3, …, n! + n are n − 1 composite numbers in a row.
Demo: record gaps up to 10 000 walks through all eleven records up to 10 000; the Record gaps button does the same for any range.
The primes on this page come from the Sieve of Eratosthenes. Why they are the building blocks: Prime Factorization. The 1 / ln n density shows up as the fading of the dots on the Ulam spiral, and ln itself is on Exponentials and Logarithms.
What the page leaves out
The proof of the prime number theorem (through the zeros of the Riemann zeta function), Riemann's explicit formula and his better guess R(x), the error bounds, primes in arithmetic progressions (Dirichlet), Chebyshev's bias and the Skewes number, ranges beyond a million, and the conjectures on gaps (Cramér, Hardy–Littlewood k-tuples) beyond naming them.