New maximal prime gaps and first occurrences

Thomas R. Nicely

http://www.trnicely.net
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.

Document History

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.

Except for the addendum (not part of the submission for publication), the content of this document is essentially that of the journal article as published; it may contain minor revisions and corrections, and differ in format and detail.

Abstract

The search for first occurrences of prime gaps, and maximal prime gaps, is extended to 1e15. New maximal prime gaps of 806 and 906 are found, and sixty-two new first occurrences are found for gaps varying in size from 676 to 906.

Mathematics Subject Classification 2000 (MSC2000)

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

Key Words and Phrases

Prime numbers, prime gaps, first occurrences, maximal gaps, maximal prime gaps.


1. Introduction

The study of the distribution of the prime numbers among the positive integers occupies a central place in number theory. This distribution may be specified by the differences G_k = p_{k+1} - p_k between successive primes; G_k is also referred to as the (prime) gap following the kth prime p_k, and the unmodified symbol G will be used to refer to a specific gap as well as the set of all prime gaps of a specified magnitude. A gap G contains (G - 1) consecutive composite integers. All gaps are even positive integers except for G(1) = 1; it is an open question whether or not gaps of magnitude 2n exist corresponding to each and every positive integer n. The first occurrence of a gap G is defined by the smallest prime p_k preceding (immediately followed by) such a gap. A (first occurrence of a) gap G is said to be maximal if all preceding gaps (between smaller consecutive primes) are strictly less than G. Thus the first occurrence of a gap of 10 follows the prime 139, but this is not a maximal gap, since an equal or larger gap (a maximal gap of 14, following 113) appears earlier in the sequence of positive integers. Note that some authors (e.g., Riesel [14, p. 80]) specify a gap by the terminating prime p_{k+1}, while others specify the size of a gap by the parameter r = G/2 (e.g., Brent [2, 3]).

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.

2. Computational Technique

The search for prime gaps is being carried out as part of a larger program [11] which includes the enumeration of the primes, twin primes, prime triplets, and prime quadruplets for (0)(1e9)(1e14); and for (1e14)(1e10)(1e15) and beyond. Also computed are the floating point (64-bit mantissa) sums and ultraprecision (53 decimal places) sums of the reciprocals of the twins, triplets, and quadruplets, in order to extrapolate estimates for the Brun's constants (limits of the sums of the reciprocals) for each constellation. All computations are being executed during slack hours on available personal computers. The number of systems (most of them Pentiums) in use has averaged about fifteen since the present program began in 1993. The source code is written in C and compiled using Borland C++ 4.52; it is written to run under Borland's 32-bit DOS extender so that all available extended memory can be used for the integer arrays. Earlier versions ran successively under DOS, Windows 3.x, and Win32s, but operation under 32-bit extended DOS proved most effective, eliminating much of the irrelevant overhead imposed by the Windows environment. Typical throughput is about 1e11 integers per day on a 60 MHz Pentium. The computations are distributed independently across the systems, currently in runs of 2e12; each interval is run in duplicate on two systems to guard against machine errors. In the event that two runs of the same interval disagree, additional runs are carried out to resolve the discrepancy. Thus far errors have been detected in more than two dozen instances, including the Pentium FDIV flaw affair [12] in the fall of 1994; faults in memory chips appear to be the most frequent culprit, although it appears impossible to completely rule out errors in either system or application or system software. The most significant independent check available is the value of pi(x), the count of primes, which has been carried out by indirect means to 1e20 by Deléglise and Rivat [6, 4]; the direct counts obtained from the present calculations agree through 1e15 with the values published by Riesel [14, p. 34 and pp. 380-383]. The first occurrences listed have also been checked directly by means of the Derive software program for DOS and Windows.

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.

3. Computational Results

Table 1 lists the first occurrences of prime gaps found in the present study, now complete to 1e15. The new maximal gaps are marked with an asterisk (*). As was pointed out above, the first occurrence and maximal gap of 804 following the prime 90874329411493 is actually due to Young and Potler [13, p. 142] and is confirmed by the present work. Presumably the other first occurrences between 7.2e13 and 9.1e13 (for the gaps of 676, 680, 686, and 718) were also known to Young and Potler, but were never published.


   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.

These results supplement those previously known and herein omitted for brevity; an exhaustive listing of previously known gaps was given by Young and Potler [17]. The smallest gap whose first occurrence is still unaccounted for is the gap of 796. First occurrences of all gaps greater than 796, not listed in Table 1, also remain to be discovered. Discovery of the new maximal gap of 906 brings us closer to the goal alluded to by Weintraub [16], that of finding the first occurrence of a gap of 1000 or greater. Motivated by a result obtained by Cramér [5], Shanks [15] conjectured that a maximal gap of magnitude M could be expected to appear at approximately exp(sqrt(M)). Riesel [14, p. 80] measures the success of this conjecture by the ratio R = ln(p_{k+1})/sqrt(M), with R expected to approach 1 as M and p_{k+1} increase without bound. For the largest known maximal gaps, R has remained near 1.13, although for the new maximal gap of 906 it attains a value of 1.0969, its absolute minimum to date. Thus, assuming that the first gap of 1000 or greater will actually be about 1050, a reasonable estimate for the location of the first occurrence of a gap of 1000 or greater would be exp(1.13*sqrt(1050)) ~ 7.98e15. The present program would not attain that level for several more years. However, this is little more than an order of magnitude estimate, since an argument could also be made for a much smaller value of exp(1.0969*sqrt(1000)) ~ 1.16e15. The discovery of the first "kilogap" thus remains difficult to anticipate.

4. Acknowledgments

The author wishes to express his appreciation to Richard P. Brent and the late Daniel Shanks, for their advice and encouragement; to Intel Corporation, for the donation of computer systems and processors; to Intel's engineers, particularly Bob Davies and Dave Papworth, for their assistance in optimizing code for the Pentium Pro; to Arjen Lenstra, whose ultraprecision routines I modified for use in my code; to Jörg Richstein, Universität Giessen, Germany, for suggesting and encouraging the addition of this line of investigation; and to the anonymous referee, for his or her helpful suggestions.


References

  1. D. Baugh and F. O'Hara, Letters to the Editor, "Large prime gaps" and "And more," J. Recreational Math. 24:3 (1992) 186-187.
  2. Richard P. Brent, "The first occurrence of large gaps between successive primes," Math. Comp. 27:124 (1973) 959-963, MR 48#8360.
  3. Richard P. Brent, "The first occurrence of certain large prime gaps," Math. Comp. 35:152 (1980) 1435-1436, MR 81g:10002.
  4. Chris Caldwell, "The prime pages," at (17 January 2002) http://www.utm.edu/research/primes/.
  5. Harald Cramér, "On the order of magnitude of the difference between consecutive prime numbers," Acta Arith. 2 (1936) 23-46.
  6. 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.
  7. Harvey Dubner, e-mail communication (04 August 1996).
  8. Harvey Dubner, e-mail communication (02 September 1996).
  9. Harvey Dubner and Harry Nelson, "Seven consecutive primes in arithmetic progression," Math. Comp. 66 (1997) 1743-1749, MR 98a:11122.
  10. L. J. Lander and T. R. Parkin, "On the first appearance of prime differences," Math. Comp. 21 (1967) 483-488, MR 37#6237.
  11. 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.
  12. Thomas R. Nicely, "RE: Pentium FDIV Flaw," electronic document available at http://www.trnicely.net/pentbug/pentbug.html.
  13. Paulo Ribenboim, "The little book of big primes," Springer-Verlag, New York, 1991, MR 92i:11008.
  14. Hans Riesel, "Prime numbers and computer methods for factorization," 2nd ed., Birkhäuser, Boston, 1994, MR 95h:11142.
  15. Daniel Shanks, "On maximal gaps between successive primes," Math. Comp. 18 (1964) 646-651, MR 29#4745.
  16. Sol Weintraub, "A prime gap of 864," J. Recreational Math. 25:1 (1993) 42-43.
  17. Jeff Young and Aaron Potler, "First occurrence prime gaps," Math. Comp. 52:185 (1989) 221-224, MR 89f:11019.
  18. Jeff Young, e-mail communication (6 June 1996).

Unpublished Addendum

NOTE: This addendum is not part of the published journal article.

Estimates For the First Kilogap

Following the submission of the final revision of the preceding paper, the first kilogap was discovered 24 January 1999 by Dr. Bertil Nyman, a Swedish nuclear physicist. Further calculations by Nyman and Nicely proved conclusively by 18 February 1999 that there was no preceding gap of 1000 or greater. This first kilogap, the first occurrence prime gap and maximal prime gap of 1132 following the prime 1693182318746371, is discussed in [20] and [21].

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 (G/ln(p_1)=35.310308) of any gap presently known; however, Nyman's gap of 1132 continues to exhibit the greatest known value of the Cramér-Shanks-Granville ratio R_csg=G/ln²(p_1), namely R_csg=0.9206386. A comprehensive and updated listing of all presently known first occurrence and maximal prime gaps is available at http://www.trnicely.net/gaps/gaplist.html. In addition, extensive tables of first known occurrence prime gaps are available at this site.

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.
==========================================================================

The Wolf and Rodriguez models appear to be the most successful. The Shanks-Cramér-Western model is seriously in error, with p-values one to two orders of magnitude too low. All models are cast in a more flattering light by calculating and comparing M given p; but that is not their relevance in the present context.


Addendum Bibliography

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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).
  6. A. E. Western, "Note on the magnitude of the difference between successive primes," J. London Math. Soc. 9 (1934) 276-278.
  7. 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.
  8. 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.
  9. Marek Wolf, e-mail communications (25 February 1998 and 11 June 1998).
  10. John W. Wrench, Jr., "Evaluation of Artin's constant and the twin-prime constant," Math. Comp. 15 (1961) 396-398, MR 23#A1619.