Prime Gaps

Letting

$$d_n\equiv p_{n+1}-p_n$$

be the Prime Difference Function, Rankin has showed that

$$d_n>{c\ln n\ln\ln n\ln\ln\ln\ln n\over(\ln\ln\ln n)^2}$$

for infinitely many $n$ and some constant $c$ (Guy 1994).

Let $p(d)$ be the smallest Prime following $d$ or more consecutive Composite Numbers. The largest known is

$$p(804)=90,874,329,412,297.$$

The largest known prime gap is of length 4247, occurring following $10^{314}-1929$ (Baugh and O'Hara 1992), although this gap is almost certainly not maximal (i.e., there probably exists a smaller number having a gap of the same length following it).

Let $c(n)$ be the smallest starting Integer $c(n)$ for a run of $n$ consecutive Composite Numbers, also called a Composite Run. No general method other than exhaustive searching is known for determining the first occurrence for a maximal gap, although arbitrarily large gaps exist (Nicely 1998). Cramér (1937) and Shanks (1964) conjectured that a maximal gap of length $n$ appears at approximately $\mathop{\rm exp}\nolimits (\sqrt{n}\,)$. Wolf conjectures that the maximal gap of length $n$ appears approximately at

$${n\over\pi(n)}[2\ln\pi(n)-\ln n+\ln(2C_2)],$$

where $\pi(n)$ is the Prime Counting Function and $C_2$ is the Twin Primes Constant.

The first few $c(n)$ for $n=1$, 2, ... are 4, 8, 8, 24, 24, 90, 90, 114, ... (Sloane's A030296). The following table gives the same sequence omitting degenerate runs which are part of a run with greater $n$, and is a complete list of smallest maximal runs up to $10^{15}$. $c(n)$ in this table is given by Sloane's A008950, and $n$ by Sloane's A008996. The ending integers for the run corresponding to $c(n)$ are given by Sloane's A008995. Young and Potler (1989) determined the first occurrences of prime gaps up to 72,635,119,999,997, with all first occurrences found between 1 and 673. Nicely (1998) extended the list of maximal prime gaps to a length of 915, denoting gap lengths by the difference of bounding Primes, $c(n)-1$.

$n$	$c(n)$	$n$	$c(n)$
1	4	319	2,300,942,550
3	8	335	3,842,610,774
5	24	353	4,302,407,360
7	90	381	10,726,904,660
13	114	383	20,678,048,298
17	524	393	22,367,084,960
19	888	455	25,056,082,088
21	1,130	463	42,652,618,344
33	1,328	467	127,976,334,672
35	9,552	473	182,226,896,240
43	15,684	485	241,160,024,144
51	19,610	489	297,501,075,800
71	31,398	499	303,371,455,242
85	155,922	513	304,599,508,538
95	360,654	515	416,608,695,822
111	370,262	531	461,690,510,012
113	492,114	533	614,487,453,424
117	1,349,534	539	738,832,927,928
131	1,357,202	581	1,346,294,310,750
147	2,010,734	587	1,408,695,493,610
153	4,652,354	601	1,968,188,556,461
179	17,051,708	651	2,614,941,710,599
209	20,831,324	673	7,177,162,611,713
219	47,326,694	715	13,828,048,559,701
221	122,164,748	765	19,581,334,192,423
233	189,695,660	777	42,842,283,925,352
247	191,912,784	803	90,874,329,411,493
249	387,096,134	805	171,231,342,420,521
281	436,273,010	905	218,209,405,436,543
287	1,294,268,492	915	1,189,459,969,825,483
291	1,453,168,142

See also Jumping Champion, Prime Constellation, Prime Difference Function, Shanks' Conjecture

References

Baugh, D. and O'Hara, F. ``Large Prime Gaps.'' J. Recr. Math. 24, 186-187, 1992.

Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, pp. 133-134, 1994.

Bombieri, E. and Davenport, H. ``Small Differences Between Prime Numbers.'' Proc. Roy. Soc. A 293, 1-18, 1966.

Brent, R. P. ``The First Occurrence of Large Gaps Between Successive Primes.'' Math. Comput. 27, 959-963, 1973.

Brent, R. P. ``The Distribution of Small Gaps Between Successive Primes.'' Math. Comput. 28, 315-324, 1974.

Brent, R. P. ``The First Occurrence of Certain Large Prime Gaps.'' Math. Comput. 35, 1435-1436, 1980.

Cramér, H. ``On the Order of Magnitude of the Difference Between Consecutive Prime Numbers.'' Acta Arith. 2, 23-46, 1937.

Guy, R. K. ``Gaps between Primes. Twin Primes'' and ``Increasing and Decreasing Gaps.'' §A8 and A11 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 19-23 and 26-27, 1994.

Lander, L. J. and Parkin, T. R. ``On First Appearance of Prime Differences.'' Math. Comput. 21, 483-488, 1967.

Nicely, T. R. ``New Maximal Prime Gaps and First Occurrences.'' http://lasi.lynchburg.edu/Nicely_T/public/gaps/gaps.htm. To Appear in Math. Comput.

Shanks, D. ``On Maximal Gaps Between Successive Primes.'' Math. Comput. 18, 646-651, 1964.

Sloane, N. J. A. Sequences A008950, A008995, A008996, and A030296 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Wolf, M. ``First Occurrence of a Given Gap Between Consecutive Primes.'' http://rose.ift.uni.wroc.pl/~mwolf.

Young, J. and Potler, A. ``First Occurrence Prime Gaps.'' Math. Comput. 52, 221-224, 1989.