TOPICS
Search

Prime Gaps


A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes. Therefore, the difference between two successive primes p_k and p_(k+1) bounding a prime gap of length n is p_(k+1)-p_k=n, where p_k is the kth prime number. Since the prime difference function

 d_k=p_(k+1)-p_k
(1)

is always even (except for p_1=2), all primes gaps >1 are also even. The notation p(n) is commonly used to denote the smallest prime p_k corresponding to the start of a prime gap of length n, i.e., such that p(n)=p_k is prime, p(n)+1, p(n)+2, ..., p(n)+n-1 are all composite, and p_(k+1)=p(n)+n is prime (with the additional constraint that no smaller number satisfying these properties exists).

The maximal prime gap G(N) is the length of the largest prime gap that begins with a prime p_k less than some maximum value N. For n=1, 2, ..., G(10^n) is given by 4, 8, 20, 36, 72, 114, 154, 220, 282, 354, 464, 540, 674, 804, 906, 1132, ... (OEIS A053303).

Arbitrarily large prime gaps exist. For example, for any n>1, the numbers n!+2, n!+3, ..., n!+n are all composite (Havil 2003, p. 170). However, no general method more sophisticated than an exhaustive search is known for the determination of first occurrences and maximal prime gaps (Nicely 1999).

PrimeGaps

Cramér (1937) and Shanks (1964) conjectured that

 p(n)∼exp(sqrt(n)).
(2)

Wolf conjectures a slightly different form

 p(n)∼sqrt(n)exp(sqrt(n)),
(3)

which agrees better with numerical evidence.

Wolf conjectures that the maximal gap G(n) between two consecutive primes less than n appears approximately at

 G(n)∼n/(pi(n))[2lnpi(n)-lnn+ln(2C_2)]=g(n),
(4)

where pi(n) is the prime counting function and C_2 is the twin primes constant. Setting pi(n)∼n/lnn reduces to Cramer's conjecture for large n,

 G(n)∼(lnn)^2.
(5)

It is known that there is a prime gap of length 803 following 90874329411493, and a prime gap of length 4247 following 10^(314)-1929 (Baugh and O'Hara 1992). H. Dubner (2001) discovered a prime gap of length 119738 between two 3396-digit probable primes. On Jan. 15, 2004, J. K. Andersen and H. Rosenthal found a prime gap of length 1001548 between two probabilistic primes of 43429 digits each. In January-May 2004, Hans Rosenthal and Jens Kruse Andersen found a prime gap of length 2254930 between two probabilistic primes with 86853 digits each (Anderson 2004).

The merit of a prime gap compares the size of a gap to the local average gap, and is given by (p_(n+1)-p_n)/(lnp_n). In 1999, the number 1693182318746371 was found, with merit 32.2825. This remained the record merit until 804212830686677669 was found in 2005, with a gap of 1442 and a merit of 34.9757. Andersen maintains a list of the top 20 known merits. The prime gaps of increasing merit are 2, 3, 7, 113, 1129, 1327, 19609, ... (OEIS A111870).

Young and Potler (1989) determined the first occurrences of prime gaps up to 72635119999997, with all first occurrences found between 1 and 673. Nicely (1999) has extended the list of maximal prime gaps. The following table gives the values of p(n) for small n, omitting degenerate runs which are part of a run with greater n (OEIS A005250 and A002386).

np(n)np(n)
123544302407359
2338210726904659
4738420678048297
62339422367084959
88945625056082087
1411346442652618343
18523468127976334671
20887474182226896239
221129486241160624143
341327490297501075799
369551500303371455241
4415683514304599508537
5219609516416608695821
7231397532461690510011
86155921534614487453523
96360653540738832927927
1123702615821346294310749
1144921135881408695493609
11813495336021968188556461
13213572016522614941710599
14820107336747177162611713
154465235371613829048559701
1801705170776619581334192423
2102083132377842842283925351
2204732669380490874329411493
222122164747806171231342420521
234189695659906218209405436543
2481919127839161189459969825483
2503870961339241686994940955803
28243627300911321693182318746371
2881294268491118443841547845541059
2921453168141119855350776431903243
3202300942549122080873624627234849
3363842610773

Define

 Delta=lim inf_(n)(p_(n+1)-p_n)/(lnp_n)
(6)

as the infimum limit of the ratio of the nth prime difference to the natural logarithm of the nth prime number. If there are an infinite number of twin primes, then Delta=0. This follows since it must then be true that d_n=2 infinitely often, say at n=n(k) for k=1, 2, ..., so a necessary condition for the twin prime conjecture to hold is that

Delta=lim inf_(n->infty)(d_n)/(lnp_n)
(7)
<=lim inf_(k->infty)(d_(n(k)))/(lnp_(n(k)))
(8)
=lim_(k->infty)2/(lnp_(n(k)))
(9)
=0.
(10)

However, this condition is not sufficient, since the same proof works if 2 is replaced by any constant.

Hardy and Littlewood showed in 1926 that, subject to the truth of the generalized Riemann hypothesis, Delta<=2/3. This was subsequently improved by Rankin (again assuming the generalized Riemann hypothesis) to Delta<=3/5. In 1940, Erdős used sieve theory to show for the first time with no assumptions that Delta<1. This was subsequently improved to 15/16 (Ricci), (2+sqrt(3))/8=0.46650... (Bombieri and Davenport 1966), and (2sqrt(2)-1)/4=0.45706... (Pil'Tai 1972), as quoted in Le Lionnais (1983, p. 26). Huxley (1973, 1977) obtained 1/4+pi/16=0.44634..., which was improved by Maier in 1986 to Delta<=0.2486, which was the best result known until 2003 (American Institute of Mathematics).

At a March 2003 meeting on elementary and analytic number theory in Oberwolfach, Germany, Goldston and Yildirim presented an attempted proof that Delta=0. While the original proof turned out to be flawed (Mackenzie 2003ab), the result has now been established by a new proof (American Institute of Mathematics 2005, Cipra 2005, Devlin 2005, Goldston et al. 2005ab).


See also

Cramér-Granville Conjecture, Jumping Champion, Nearest Prime, Prime Constellation, Prime Difference Function, Prime Distance, Shanks' Conjecture, Twin Composites, Twin Primes

Explore with Wolfram|Alpha

References

American Institute of Mathematics. "Small Gaps between Consecutive Primes: Recent Work of D. Goldston and C. Yildirim." http://www.aimath.org/goldston_tech/.American Institute of Mathematics. "Breakthrough in Prime Number Theory." May 24, 2005. http://aimath.org/.Andersen, J. K. "First Known Prime Megagap." http://hjem.get2net.dk/jka/math/primegaps/megagap.htm.Andersen, J. K. "Largest Known Prime Gap." http://hjem.get2net.dk/jka/math/primegaps/megagap2.htm.Andersen, J. K. "A Prime Gap of 1001548." 15 Jan 2004. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0401&L=nmbrthry&F=&S=&P=397.Andersen, J. K. "A Prime Gap of 2254930." 2 Jun 2004. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0406&L=nmbrthry&P=601.Andersen, J. K. "Top-20 Prime Gaps." http://hjem.get2net.dk/jka/math/primegaps/gaps20.htm.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.Caldwell, C. "The Gaps Between Primes." http://primes.utm.edu/notes/gaps.html.Cipra, B. "Proof Promises Progress in Prime Progressions." Science 304, 1095, 2004.Cipra, B. "Third Time Proves Charm for Prime-Gap Theorem." Science 308, 1238, 2005.Cramér, H. "On the Order of Magnitude of the Difference between Consecutive Prime Numbers." Acta Arith. 2, 23-46, 1937.Cutter, P. A. "Finding Prime Pairs with Particular Gaps." Math. Comput. 70, 1737-1744, 2001.Devlin, K. "Major Advance on the Twin Primes Conjecture." May 24, 2005. http://www.maa.org/news/052505twinprimes.html.Dubner, H. "New Large Prime Gap Record." 13 Dec 2001. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0112&L=nmbrthry&P=1093.Fouvry, É. "Autour du théorème de Bombieri-Vinogradov." Acta. Math. 152, 219-244, 1984.Fouvry, É. and Grupp, F. "On the Switching Principle in Sieve Theory." J. reine angew. Math. 370, 101-126, 1986.Fouvry, É. and Iwaniec, H. "Primes in Arithmetic Progression." Acta Arith. 42, 197-218, 1983.Goldston, D. A.; Graham, S. W.; Pintz, J.; and Yildirim, C. Y. "Small Gaps between Primes or Almost Primes." Jun. 3, 2005a. http://www.arxiv.org/abs/math.NT/0506067/.Goldston, D. A.; Motohashi, Y.; Pintz, J.; and Yildirim, C. Y. "Small Gaps between Primes Exist." May 14, 2005b. http://www.arxiv.org/abs/math.NT/0505300/.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.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, 2003.Huxley, M. N. "Small Differences between Consecutive Primes." Mathematica 20, 229-232, 1973.Huxley, M. N. "Small Differences between Consecutive Primes. II." Mathematica 24, 142-152, 1977.Lander, L. J. and Parkin, T. R. "On First Appearance of Prime Differences." Math. Comput. 21, 483-488, 1967.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, 1983.Mackenzie, D. "Prime Proof Helps Mathematicians Mind the Gaps." Science 300, 32, 2003a.Mackenzie, D. "Prime-Number Proof's Leap Falls Short." Science 300, 1066, 2003b.Montgomery, H. "Small Gaps Between Primes." 13 Mar 2003. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0303&L=nmbrthry&P=1323.Nicely, T. R. "First Occurrence Prime Gaps." http://www.trnicely.net/gaps/gaplist.html.Nicely, T. R. "New Maximal Prime Gaps and First Occurrences." Math. Comput. 68, 1311-1315, 1999. http://www.trnicely.net/gaps/gaps.html.Nicely, T. R. and Nyman, B. "First Occurrence of a Prime Gap of 1000 or Greater." http://www.trnicely.net/gaps/gaps2.html.Nyman, B. and Nicely, T. R. "New Prime Gaps Between 10^(15) and 5×10^(16)." J. Int. Seq. 6, 1-6, 2003.Rivera, C. "Problems & Puzzles: Puzzle 011-Distinct, Increasing & Decreasing Gaps." http://www.primepuzzles.net/puzzles/puzz_011.htm.Shanks, D. "On Maximal Gaps between Successive Primes." Math. Comput. 18, 646-651, 1964.Sloane, N. J. A. Sequences A002386/M0858, A008996, A008950, A008995, A008996, A030296, A053303, and A111870 in "The On-Line Encyclopedia of Integer Sequences."Soundararajan, K. "Small Gaps Between Prime Numbers: The Work of Goldston-Pintz-Yildirim." Bull. Amer. Math. Soc. 44, 1-18, 2007.Wolf, M. "First Occurrence of a Given Gap between Consecutive Primes." http://www.ift.uni.wroc.pl/~mwolf/.Wolf, M. "Some Conjectures on the Gaps Between Consecutive Primes." http://www.ift.uni.wroc.pl/~mwolf/.Young, J. and Potler, A. "First Occurrence Prime Gaps." Math. Comput. 52, 221-224, 1989.

Referenced on Wolfram|Alpha

Prime Gaps

Cite this as:

Weisstein, Eric W. "Prime Gaps." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PrimeGaps.html

Subject classifications