|Our book "Prime Curios! The Dictionary of Prime Number Trivia" is now available on CreateSpace, Amazon, ....|
pn+1 = pn + g(pn) + 1.That is, g(pn) is the (size of) gap between pn and pn+1.
By the prime number theorem we know there are approximately n/log(n) (natural log) primes less than n, so the "average gap" between primes less than n is log(n). But how wide of range can these gaps have? We will discuss several aspects of this question below.
Second note that g(p) can be arbitrarily large. To see this let n be any integer greater than one and consider the following sequence of consecutive integers:
n!+2, n!+3, n!+4, n!+5, ..., n!+nNotice that 2 divides the first, 3 divides the second, ..., n divides the n-1st, showing all of these numbers are composite! So if p is the largest prime less than n!+2 we have g(p) > n-1. Obviously there should be smaller numbers which produce the same gaps. For example, there is a gap of 777 composites after the prime 42842283925351--this is the least prime which produces a gap of 777 and it is far smaller than 778!+2 (which has 1914 digits). (Rather than use n!, one can also use the smaller n primorial: n#).
In the last paragraph we showed that lim sup g(n) = infinity, but we expect much more since the "average gap" is about log(n). In 1931 Westzynthius [Westzynthius31] proved that
lim sup g(n)/log pn = infinitywhich means that for every ß>0 there are infinitely many primes p with g(p) > ß log p. Before we say more we should look at some numerical evidence.
For each non-negative integer g let p(g) be the smallest prime that is followed by at least g composites. This table tells us p(148) = p(149) = ... = p(153) = 4652353. See [Nicely99] and [NN99] for information on searches which extended this table to maximal gaps through 1132. We give a more complete list of maximal gaps on a separate page. See also Jens Kruse Andersen's page of top twenty gaps.
For the values in the table above we have graphed log p(g) (the natural log) versus g in the graph on the right. Perhaps you can begin to see why Shanks conjectured in 1964 that
log p(g) ~ sqrt(g),and Weintraub estimated in 1991 that
prime number theorem we can show that for every real number e > 0 and there is some integer m0 such that there is always a prime p satisfying
m < p < (1 + e)m (for every m > m0)This shows that g(p)<ep for all p>max(m0,1+1/e). Or more succinctly, g(pn)<epn for n>n0. Here are several specific pairs e, n0 quoted from [Ribenboim95 p252-253]:
Various upper bounds for lim inf g(p)/logp have been found, including 0.248 [Maier85] (of course, both the twin prime conjecture and the prime k-tuple conjectures require that the limit inferior be zero). In a related conjecture Cramér [Cramér36] conjectured that
lim sup g(p)/(log p)2 = 1.
Granville altered Cramer's conjecture, suggesting that it underestimates the size of the gaps. Granville conjectures that for any constant c less than Euler's gamma:
g(p) > 2 e-c log2 p
infinitely often. Here the constant comes from analogy with Merten's theorem.Can this be proven? Not yet, but Cramér did show that if the Riemann Hypothesis holds, then we would have the far weaker result:
g(p) < k p1/2 log p.There is a lot more to say concerning conjectures and theorems on both the size of these gaps and how often a given gap occurs... Why not just spend an evening with section 4.2 ("The nth Prime and Gaps") of [Ribenboim95].
Another prime page by Chris K. Caldwell <firstname.lastname@example.org>