Thomas R. Nicely

Current e-mail address

Freeware copyright (c) 2009 Thomas R. Nicely. Released into the public domain by the author, who disclaims any legal liability arising from its use.

Last modified....................0558 GMT 05 October 2009. Journal citation.................Mathematics of Computation 68:227 (July, 1999) 1311-1315. Mathematical Reviews.............MR1627813 (99i:11004). AMS E-math posting...............13 February 1999 (PI: S 0025-5718(99)01065-0). Accepted for publication.........21 February 1998. Acknowledgment of revision.......05 December 1997. Revision submitted...............01 December 1997. Acknowledgment of submission.....16 June 1997. Original submission..............13 June 1997.

Secondary: 11-04, 11Y11, 11Y99.

No general method more sophisticated than an exhaustive search is known for the determination of first occurrences and maximal prime gaps. As in the present study, this is most efficiently done by sieving successive blocks of positive integers for primes, recording the successive differences, and thus determining directly the first occurrences and maximal gaps. This technique has been used by Shanks [15], Lander and Parkin [10], Brent [2, 3], and Young and Potler [17] to extend the search through all primes < 7.263512e13. Thus all first occurrences of gaps through 674, as well as scattered first occurrences for gaps through 778, were tabulated, and all maximal prime gaps through 778 were located. See Young and Potler [17] for an exhaustive listing of these previous results. In addition, Young and Potler continued their calculations to an unpublished higher level; Ribenboim [13, p. 142] credits them with the discovery of an additional maximal prime gap of 804 following the prime 90874329411493, and this was confirmed by Young [18].

Isolated occurrences of much larger prime gaps have been found. It is well known that arbitrarily large gaps exist, for the positive integer (n! + 1) must be followed by at least (n - 1) consecutive composite integers; but no instance of this formula beyond n=5 (first occurrence and maximal gap of 14 following 113) is known to yield a first occurrence. Weintraub [16] has discovered a gap of 864 following 6505941701960039, and Baugh and O'Hara [1] discovered a gap of 4248 following 1e314 - 1929, but these are not known or believed to be maximal gaps or even first occurrences; the present work demonstrates conclusively that Weintraub's gap is not maximal. In conjunction with the search for seven consecutive primes in arithmetic progression [9], Dubner has discovered [7] a gap of 1092 following the prime 409534375009657239721; this is the first known occurrence of a gap of 1000 or greater, but again it is not known to be maximal or a first occurrence. Dubner also reports [8] a gap of 12540 following the 385-digit prime

1028115851618596629291338345969573325611755920349536050557212232499\ 6950065379512197585317961759000690328913319244717897688019822063737812\ 5686339726137874956095491930654497693978715833794999935477468391789508\ 3444495414063479003554272907008549459458538251939796513140998638325548\ 2457633841427250249367844894786016514356294279402896163593801089250404\ 09462881632270278716570882306451587569.

It is of interest to note that two of the Pentiums in service are P5-60 systems with (FDIV) flawed CPUs; the flawed floating point divisions and remainders are being detected and corrected in real time, using a combination of the -fp switch in Borland C++ 4.52 and a custom procedure (C function) which traps suspect divisors in all fmod and fmodl remaindering calls. With these errors trapped and corrected, and their results checked against runs on CPUs free of the flaw, these two systems have remained error free for more than a year.

Table 1. First occurrence prime gaps in 7.2e13 < p < 1e15. =============================================================== Gap Following the Gap Following the prime prime =============================================================== 676 78610833115261 782 726507223559111 680 82385435331119 784 497687231721157 686 74014757794301 786 554544106989673 688 110526670235599 788 96949415903999 704 97731545943599 790 678106044936511 708 143679495784681 792 244668132223727 710 138965383978937 794 673252372176533 712 106749746034601 798 309715100117419 718 82342388119111 800 486258341004083 720 111113196467011 802 913982990753641 722 218356872845927 804* 90874329411493 726 156100489308167 806* 171231342420521 732 140085225001801 808 546609721879171 734 154312610974979 810 518557948410967 736 161443383249583 814 827873854500949 738 143282994823909 816 632213931500513 742 189442329715069 818 860149012919321 746 184219698008123 820 497067290087413 748 172373989611793 822 799615339016671 750 145508250945419 826 407835172832953 752 255294593822687 828 807201813046091 754 219831875554399 830 507747400047473 760 98103148488133 832 243212983783999 762 144895907074481 834 743844653663833 764 323811481625339 836 880772773476623 768 423683030575549 840 670250273356109 770 214198375528463 844 782685877447783 772 186129514280467 860 844893392671019 774 469789142849483 862 425746080787897 776 187865909338091 872 455780714877767 780 471911699384963 880 277900416100927 906* 218209405436543 =============================================================== *Maximal gap.

- D. Baugh and F. O'Hara, Letters to the Editor, "Large prime gaps" and "And more," J. Recreational Math. 24:3 (1992) 186-187.
- Richard P. Brent, "The first occurrence of large gaps between successive primes," Math. Comp. 27:124 (1973) 959-963, MR 48#8360.
- Richard P. Brent, "The first occurrence of certain large prime gaps," Math. Comp. 35:152 (1980) 1435-1436, MR 81g:10002.
- Chris Caldwell, "The prime pages," at (17 January 2002) http://www.utm.edu/research/primes/.
- Harald Cramér, "On the order of magnitude of the difference between consecutive prime numbers," Acta Arith. 2 (1936) 23-46.
- Marc Deléglise and Joël Rivat, "Computing pi(x): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method," Math. Comp. 65 (1996) 235-245, MR 96d:11139.
- Harvey Dubner, e-mail communication (04 August 1996).
- Harvey Dubner, e-mail communication (02 September 1996).
- Harvey Dubner and Harry Nelson, "Seven consecutive primes in arithmetic progression," Math. Comp. 66 (1997) 1743-1749, MR 98a:11122.
- L. J. Lander and T. R. Parkin, "On the first appearance of prime differences," Math. Comp. 21 (1967) 483-488, MR 37#6237.
- Thomas R. Nicely, "Enumeration to 1e14 of the twin primes and Brun's constant," Virginia Journal of Science 46:3 (Fall, 1995) 195-204, MR1401560 (97e:11014). Electronic reprint available at http://www.trnicely.net/twins/twins.html.
- Thomas R. Nicely, "RE: Pentium FDIV Flaw," electronic document available at http://www.trnicely.net/pentbug/pentbug.html.
- Paulo Ribenboim, "The little book of big primes," Springer-Verlag, New York, 1991, MR 92i:11008.
- Hans Riesel, "Prime numbers and computer methods for factorization," 2nd ed., Birkhäuser, Boston, 1994, MR 95h:11142.
- Daniel Shanks, "On maximal gaps between successive primes," Math. Comp. 18 (1964) 646-651, MR 29#4745.
- Sol Weintraub, "A prime gap of 864," J. Recreational Math. 25:1 (1993) 42-43.
- Jeff Young and Aaron Potler, "First occurrence prime gaps," Math. Comp. 52:185 (1989) 221-224, MR 89f:11019.
- Jeff Young, e-mail communication (6 June 1996).

Succeeding maximal prime gaps have been discovered by Nyman (of
measure 1184), by Professor
Tomás Oliveira e Silva (1198, 1220, 1224, 1248, 1272, and
1328), by
Professor Donald E. Knuth of Stanford University (gaps of 1356 and
1370), and by Siegfried
"Zig" Herzog (a gap of 1442), using Silva's computer codes. Most
recently, Silva discovered (01 April 2009, verified maximal 24 July 2009)
a maximal gap of 1476 following the prime 1425172824437699411. Silva's
new maximal gap of 1476 exhibits the greatest merit

It is instructive to compare the empirically discovered location of the first kilogap, and the succeeding maximal gaps, with the values predicted by various models attempting to describe the distribution of maximal prime gaps. These models include that of Shanks (motivated by a result of Cramér), as expounded in [15] and [5], and as foreshadowed in the work of A. E. Western [24]:

[SCW] p ~ exp(sqrt(M)) ,

where p is the predicted location of the maximal prime gap M; more precisely, the predicted initiating prime p_1 is taken as the largest prime not exceeding the right hand side. The model expounded by Nicely (motivated by the work of Riesel ([14], p. 80) in the main paper was

[NR] p ~ exp(1.13*sqrt(M)) .

Dr. Marek Wolf has conjectured a number of models [25, 26, 27], of which we mention the following:

[Wolf] p ~ sqrt(M)*exp(0.5*sqrt(4*M + (ln(M))^2)) .

Finally, Luis Rodriguez (Abreu/Torres) conjectures [22] that

[Rodriguez] M ~ (ln(p) - ln(ln(p)))^2 ;

Rodriguez's formula defines p as a non-elementary function of M, necessitating approximate solutions by iteration.

Following is a comparison of the estimates obtained from each model, for a (hypothetical) maximal gap of 1000, and for the succeeding maximal prime gaps since discovered. For each maximal gap measure M, the actual value of the initiating prime p_1 is shown, followed by the predictions from each model.

========================================================================== M Actual p_1 Wolf Rodriguez SCW** Nicely-Riesel ========================================================================== 1000$ 1.69e15 2.07e15 1.91e15 5.41e13 3.30e15 1132 1.69e15 1.65e16 1.52e16 4.09e14 3.25e16 1184 4.38e16 3.62e16 3.34e16 8.79e14 7.70e16 1198 5.54e16 4.46e16 4.12e16 1.08e15 9.68e16 1220 8.09e16 6.18e16 5.70e16 1.48e15 1.38e17 1224 2.04e17 6.55e16 6.04e16 1.56e15 1.48e17 1248 2.18e17 9.30e16 8.58e16 2.20e15 2.17e17 1272 3.05e17 1.32e17 1.21e17 3.08e15 3.18e17 1328 3.53e17 2.92e17 2.69e17 6.71e15 7.65e17 1356 4.01e17 4.32e17 3.98e17 9.83e15 1.18e18 1370 4.18e17 5.24e17 4.84e17 1.19e16 1.46e18 1442 8.04e17 1.40e18 1.29e18 3.10e16 4.32e18 1476 1.43e18 2.21e18 2.04e18 4.84e16 7.15e18 ========================================================================== **Shanks-Cramer-Western. $Hypothetical maximal gap. ==========================================================================

- Richard P. Brent, "Irregularities in the distribution of primes and twin primes," Math. Comp. 29:129 (1975) 43-56, MR 51#5522. Corrigendum ibid. 30:133 (1976) 198, MR 53#302. Addendum reviewed ibid. 30 (1976) 379.
- Thomas R. Nicely and Bertil Nyman, "First occurrence of a prime gap of 1000 or greater," unpublished (May, 1999), available electronically at http://www.trnicely.net/gaps/gaps2.html.
- Bertil Nyman and Thomas R. Nicely, "New prime gaps between 1e15 and 5e16," Journal of Integer Sequences 6 (2003), Article 03.3.1, 6 pp. (electronic), MR1997838 (2004e:11143). Available in various formats (PS, PDF, dvi, AMS-LaTeX2e) at the home page of the Journal of Integer Sequences.
- Luis Rodriguez (AKA Luis Rodriguez Abreu/Torres), e-mail communication (15/18 January 1999). Also noted (17 January 2002) at http://www.utm.edu/research/primes/notes/errata/index.html.
- Tomás Oliveira e Silva, research project in progress. Numerical verification of the Goldbach conjecture to a large upper bound, with collateral counts of primes, twin primes, and prime gaps. E-mail communications (2001-2009).
- A. E. Western, "Note on the magnitude of the difference between successive primes," J. London Math. Soc. 9 (1934) 276-278.
- Marek Wolf, "Unexpected regularities in the distribution of prime numbers," preprint (May, 1996) available electronically (May, 1999) at http://www.ift.uni.wroc.pl/~mwolf.
- Marek Wolf, "First occurrence of a given gap between consecutive primes," preprint (April, 1997) available electronically (May, 1999) at http://www.ift.uni.wroc.pl/~mwolf.
- Marek Wolf, e-mail communications (25 February 1998 and 11 June 1998).
- John W. Wrench, Jr., "Evaluation of Artin's constant and the twin-prime constant," Math. Comp. 15 (1961) 396-398, MR 23#A1619.

- Top of page
- "New prime gaps between 1e15 and 5e16"
- "First occurrence of a prime gap of 1000 or greater"
- Listing of all known first occurrence and maximal prime gaps
- Tables of first known occurrence prime gaps
- Home page