And now for something completely different... [Cue the Monty Python theme music]
Gaps in the Prime Number Sequence
Primes are the Building Blocks
The prime numbers
are of fundamental interest because they are the multiplicative building blocks
for all the positive integers. The sequence begins
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ...
The missing numbers are products of collections of primes. Because they are composed of primes, they are called composite
numbers, or "composites" for short (just as prime numbers are called "primes" for short).
Every composite is the product os a unique
collection of primes. A few early instances:
2x2 = 4, 2x3 = 6, 3x3 = 9, 2x2x3 = 12, 3x3x3 = 27, 2x3x5 = 30,
3x17 = 51, 2x2x2x2x2x2 = 64, 3x29 = 87, 7x13 = 91, 7x17 = 119, 11x13 = 143, ...
Can you decide whether 1001 is prime or composite? How about 8629, 8631 and 8633? (Hint: just one is prime.) That brings us to the next topic.
Factorising is Hard
The general problem of deciding whether a large number is prime or composite is notoriously difficult. Even if
a given number is known to be composite, finding its prime factors can still be extremely difficult.
Using this principle, there are codes which can be constructed in which a large number A is the basis for the code, and the decryption of any secret message in that code can only be done if the receiver knows the prime factors of A. It is relatively straightforward to take two very large prime numbers B and C and multiply them together to construct A = BxC. An authorised recipient is told the numbers B and C, so can decode messages which use A as their basis. An unauthorised interceptor of messages might know the number A, but in order to decrypt the messages the number A would first have to be factorised into the prime product BxC to reveal the B and C essential for decryption. For the code maker, multiplying known primes B and C together "easily" gives A, but for an eavesdropper, unscrambling the egg to take A apart and recover the prime factors B and C is vastly more difficult...
Gaps between Primes
The gaps between consecutive primes are one of the first things that attract our attention when we look at the sequence of primes and try to discern patterns in that sequence. After 2, all subsequent primes are odd numbers, so the gap between any two is even:
3 - 2 = 1, 5 - 3 = 2, 7 - 5 = 2, 11 - 7 = 4, 13 - 11 = 2, 17 - 13 = 4, ...
So, after the first term 1, the "first difference" sequence for the primes only has even terms:
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, ...
On average, the gap terms increase in size. However, it seems there is no end to the terms equal to "2" in the sequence, but no one has been able to prove or disprove that. (Each "2" corresponds to a pair of consecutive odd numbers which are both prime. These are twin primes
, and the Twin Prime Conjecture
predicts that such pairs occur endlessly in the sequence of primes.)
It is easy to show that the gap between consecutive primes can be larger than any chosen number. Let me give a concrete example by showing that there must be consecutive primes with difference at least 10.
First construct the number M = 2x3x5x7 = 210, made from the first four primes. Consider the nine consecutive numbers
M + 2, M + 3, M + 4, ..., M + 10.
Since M is a multiple of 2, so M + 2, M + 4, M + 6, M + 8, M + 10 must all be multiples of 2; therefore they are all composite. Since M is a multiple of 3, so M + 3, M + 6, M + 9 must be multiples of 3; therefore they are all composite. Since M is a multiple of 5, so M + 5 and M + 10 must be multiples of 5, so are composite. Since M is a multiple of 7, so is M + 7, and therefore M + 7 is composite. This shows that
M + 2, M + 3, M + 4, ..., M + 10
are all composite. Let p be the largest prime number less than M + 2, and q be the smallest prime number greater than M + 10. Then p and q are consecutive primes, with difference q - p is at least (M + 11) - (M + 1) = 10. Hence p and q are a pair of consecutive primes that differ by at least 10.
In this concrete example, M + 1 = 211 is the prime p. It turns out that M + 11 = 221 = 13x17 is composite, as is M + 12 = 222 = 2x3x37, but M + 13 = 223 is the prime q, so in this case q - p = 223 - 211 = 12. The construction only ensured that we would find a "gap" of size at least 10, but in practice we have found the consecutive primes 211 and 223, with a gap of size 12,
Now notice that if M* is the result of multiplying M by any power of 2, the same reasoning shows that M* + 2, M* + 4, M* + 6, M* + 8, M* + 10 are all multiples of 2, so are composite; M* + 3, M* + 6, M* + 9 are all multiples of 3, so composite; M* + 5, M* + 10 are multiples of 5, so composite; and M* + 7 is a multiple of 7, so composite. Hence there are no primes in the nine consecutive numbers M* + 2, M* + 3, ..., M* + 10. If p* is the largest prime less than M* + 2, and q* is the smallest prime greater than M* + 10, then q* - p* ≥ 10. Because there are infinitely many choices for M*, it follows that there are infinitely many pairs of consecutive primes with difference 10 or more.
As a few concrete examples, the construction leads us to discover that
421 and 431 are consecutive primes, with difference 10;
839 and 853 are consecutive primes, with difference 14;
1669 and 1693 are consecutive primes, with difference 24.
if M* = 2M = 420, then M* + 1 = p* = 421 and M* + 11 = q* = 431, so q* - p* = 10;
if M* = 4M = 840, then M* + 1 = 841 = 29x29, so M* - 1 = p* = 839; M* + 11 = 851 = 23x37,
so M* + 13 = q* = 853;
then q* - p* = 14;
if M* = 8M = 1680, then we have a remarkable patch of composites:
M* + 1 = 1681 = 41x41; M* - 1 = 1679 = 23x73;
tweaking the original construction shows that M* - 2, ..., M* - 10 will all be composites:
in particular, M* - 3 = 1677 = 3x13x43; M* - 5 = 1675 = 5x5x67; M* - 7 = 1673 = 7x23;
M* - 9 = 1671 = 3x557; so it turns out that M* - 11 = p* = 1669.
Also M* + 11 = 1691 = 19x89, so it turns out that M* + 13 = q* = 1693.
Then p* = 1669 and q* = 1693 are consecutive primes, with difference q* - p* = 24.
The construction of M can be modified by taking the product of any initial collection of primes, and in that generalised form it gives us a "constructive" proof that
For any chosen number N, there are infinitely many pairs of consecutive primes
with difference greater than N.
I will continue the discussion of gaps in the sequence of primes in another post.