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 3

Chebyshev’s bounds and Bertrand’s postulate

Before anyone could prove the Prime Number Theorem, Pafnuty Chebyshev proved that π(x) is within a constant factor of x/log x, and used that to prove there is always a prime between n and 2n.

Chebyshev worked with weighted counts that are easier to handle: θ(x) adds log p over primes p ≤ x, and ψ(x) adds log p over prime powers pk ≤ x. The Prime Number Theorem is equivalent to ψ(x)/x → 1.

ψ(x)/x (teal) and θ(x)/x (gold) from 10 to 10^7, log axis, inside the band 0.92129 to 1.10555 that Chebyshev proved in 1852 for ψ(x)/x at large x. Both approach 1, as the Prime Number Theorem later confirmed.
From the sieve to 107; prime powers added for ψ. At 107, ψ(x)/x = 0.99985 and θ(x)/x = 0.99952. The band constants are Chebyshev’s, as usually quoted from his 1852 memoir; his bounds hold for sufficiently large x. Motion is off if your system asks for reduced motion.
  • Settled Chebyshev (1852): 0.92129 · x ≤ ψ(x) ≤ 1.10555 · x for all large x. He also showed that if π(x)/(x/log x) has a limit at all, the limit is 1 (1848–1850).

Bertrand’s postulate

Joseph Bertrand checked by hand in 1845 that for every n up to three million there is a prime p with n < p < 2n. Chebyshev proved it for all n in 1852.

For each n from 2 to 3000, the ratio of the next prime after n to n. The ratio stays below 2 (dashed line) everywhere, as Chebyshev proved for all n ≥ 2 in 1852, and it sinks toward 1 as n grows.
Next prime after n, from the sieve, for n = 2 to 3000. The highest dot is 1.6667 at n = 3 (next prime 5). For n ≥ 25 the ratio never exceeds 1.1935 (n = 31, next prime 37) in this range. Motion is off if your system asks for reduced motion.
  • Settled Ramanujan (1919) gave a short proof, and Erdős (1932) an elementary one; the stronger statement that π(2x) − π(x) grows without bound follows from the Prime Number Theorem.
  • Open Legendre’s conjecture, that there is always a prime between n² and (n+1)², is open.