Prime gaps explained
The primes never stop, but they do spread out. Between 1 and 100 there are 25 of them; between 1,000,000 and 1,000,100 there are only 6. The distances between neighbouring primes, the prime gaps, follow a clear average and yet behave almost at random around it, and some of the oldest open questions in mathematics are about them.
What is a prime gap?
A prime gap is the difference between a prime and the next one. After 7 comes 11, a gap of 4; after 23 comes 29, a gap of 6, with the five composite numbers 24, 25, 26, 27 and 28 in between. Apart from the gap of 1 from 2 to 3, every gap is even, because every prime after 2 is odd. A gap of g means g − 1 composite numbers in a row.
The average gap is ln p
The prime number theorem, proved in 1896, says that the number of primes up to x is about x / ln x, where ln is the natural logarithm. Put the other way round, near a number p roughly one number in ln p is prime, so the average gap there is about ln p. That is about 7 near 1,000, 14 near a million and 28 near a trillion: the gaps grow, but very slowly. Up to 100,000 the average gap is 10.4, and ln 100,000 is 11.5; the average over a whole range is a little below ln of its end, because the gaps were smaller earlier on.
Small gaps and twin primes
Twin primes are pairs with a gap of 2, such as 17 and 19 or 1,000,037 and 1,000,039. They get rarer, but they seem never to run out: there are 1,224 pairs below 100,000 and 8,169 below a million. The twin prime conjecture says there are infinitely many, and it is still unproved. In 2013 Yitang Zhang proved the first result of its kind: some gap below 70 million occurs infinitely often. James Maynard and Terence Tao soon found a simpler method, and the Polymath project brought the bound down to 246.
Large gaps
Gaps can be as large as you like. Take n! = 1 × 2 × … × n: then n! + 2 is divisible by 2, n! + 3 by 3, and so on up to n! + n, which is n − 1 composite numbers in a row. Large gaps turn up much earlier than that, though. A maximal gap is one larger than every gap before it: 8 after 89, 14 after 113, 34 after 1,327, 72 after 31,397, 114 after 492,113, and 582 after 1,346,294,310,749. Computer searches have found every maximal gap below 2^64, about 1.8 × 10^19. On the other side, Bertrand's postulate, proved by Chebyshev in 1852, guarantees a prime between n and 2n, so the gap after a prime p is always smaller than p.
Cramér's conjecture and merit
In 1936 Harald Cramér modelled the primes as random numbers that each have a chance of 1 in ln n of being prime. His model predicts that the largest gaps up to p are about (ln p)², and he conjectured that they never grow faster than that. Every maximal gap found so far is below (ln p)²; the gap of 582 above, for example, is about three quarters of it. To compare gaps of different sizes, number theorists use merit, the gap divided by ln p. A merit of 1 is an average gap; 34 after 1,327 has a merit of 4.73, and the best known gaps have merits above 30.
Which gap is most common?
Small gaps are the most frequent, but not in order of size. A gap of 6 is more common than a gap of 2 or 4, because p and p + 6 can both avoid being multiples of 3, while one of p, p + 2 and p + 4 always is a multiple of 3. From 947 on, 6 is the most common gap of all; such a leader is called a jumping champion. In the histogram the multiples of 6 stand out above their neighbours. Much further out, the champion is expected to become 30 and then 210, the products of the first primes, because they avoid the multiples of 2, 3 and 5, and then also of 7.
Explore it
Open the explorer to see every gap in a range plotted at its prime, with the average ln p and Cramér's (ln p)² drawn over it. Click a dot to see the numbers in that gap, colored by their smallest factor, and step through the gaps one by one. Switch to the histogram to count each gap size, and pick a record gap, up to 582 after 1,346,294,310,749, to jump straight to it.
Frequently asked questions
Is there always a prime between two squares?
Nobody knows. Legendre's conjecture says there is a prime between n² and (n + 1)² for every n, which would mean the gap after p is roughly at most 2√p. It has been checked very far, but not proved.
Why are there no odd gaps after 2?
Every prime after 2 is odd, and the difference between two odd numbers is even. The only odd gap is the 1 between 2 and 3.
What are cousin and sexy primes?
Pairs of primes with a gap of 4, such as 7 and 11, are called cousin primes, and pairs with a gap of 6, such as 23 and 29, sexy primes, from the Latin sex for six. Like twin primes, both are expected to go on forever.
How does the explorer find the primes so fast?
It uses a segmented sieve of Eratosthenes: it lists the primes up to the square root of the end of the range, then crosses out their multiples in the range itself. A range of 10 million numbers near 2 trillion needs only the primes below about 1.4 million.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Explore prime gaps