
Our book "Prime Curios! The Dictionary of Prime Number Trivia" is now available on CreateSpace, Amazon, .... 

Contents:
1. Introduction and definition of g(n)It is frequently asked how large the gap between consecutive primes may get. Before we answer this, let us first carefully define gap (there are two different standard definitions). For every prime p let g(p) be the number of composites between p and the next prime. So letting p_{n} be the nth prime we have:p_{n}_{+1} = p_{n} + g(p_{n}) + 1.That is, g(p_{n}) is the (size of) gap between p_{n} and p_{n}_{+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. 2. lim inf g(n) = 1(?) and lim sup g(n) = infinityFirst note that g(p) = 1 for twin primes p, p+2. So from the twin prime conjecture we have the conjecture (almost certainly true) that g(p) = 1 infinitely often (or equivalently lim inf g(n) = 1).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 n1st, showing all of these numbers are composite! So if p is the largest prime less than n!+2 we have g(p) > n1. Obviously there should be smaller numbers which produce the same gaps. For example, there is a gap of 777 composites after the prime 42842283925351this 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 p_{n} = 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. 3. A Table and Graph of Record GapsIn the following table we list the maximal gaps through 381. These are the first occurrences of gaps of at least of this length. For example, there is a gap of 879 composites after the prime 277900416100927. This is the first occurrence of a gap of this length, but still is not a maximal gap since 905 composites follow the smaller prime 218209405436543 [Nicely99].
For each nonnegative 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
4. Bounds on g(p)It is possible to put an upper limit on g(p) given p. By the prime number theorem we can show that for every real number e > 0 and there is some integer m_{0} such that there is always a prime p satisfyingm < p < (1 + e)m (for every m > m_{0})This shows that g(p)<ep for all p>max(m_{0},1+1/e). Or more succinctly, g(p_{n})<ep_{n} for n>n_{0}. Here are several specific pairs e, n_{0} quoted from [Ribenboim95 p252253]:
5. What about g(p)/log p, g(p)/(log p)^{2} ?Again, the prime number theorem proves that the average value of g(p)/log p is one, but what do we know of the sequence {g(p)/logp}? Ricci [Ricci56] showed that set of limit points of this set has positive Lebesgue measure, but so far the only proven limit point is infinity (mentioned above) [see EE85, p22].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 ktuple 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} log^{2} 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 p^{1/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 <caldwell@utm.edu> 