New maximal prime gaps and first occurrences
Thomas R. Nicely
Copyright © 2007 Thomas R. Nicely. All rights reserved.
This document may be reproduced and distributed for educational
and non-profit purposes.
Document History
Last modified....................0500 EDT 27 April 2007.
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....... 5 December 1997.
Revision submitted............... 1 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 10^15. 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.263512*10^13. 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 10^314 - 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)(10^9)(10^14); and for
(10^14)(10^10)(10^15) 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 10^11 integers per day on a 60 MHz Pentium.
The computations are distributed independently across the systems,
currently in runs of 2*10^12; 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 10^20 by Deléglise and Rivat [6, 4];
the direct counts obtained from the present calculations agree through
10^15 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 10^15. 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.2*10^13 and
9.1*10^13 (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.2*10^13 < p < 10^15.
===============================================================
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.98*10^15. 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.16*10^15. 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
- 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 (4 August 1996).
- Harvey Dubner, e-mail communication (2 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 10^14 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).
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), and by
Professor Donald E. Knuth of Stanford University (gaps of 1356 and
1370). Most recently, a maximal gap of 1442 was discovered
(21 November 2005, verified maximal 26 April 2007) by
Siegfried "Zig" Herzog,
using Silva's computer codes. 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$ 1693182318746371 2066666636621333 1905173638543079 54149865291649 3303429479300323
1132 1693182318746371 16535417187791797 15247840952326579 409192852367737 32469730507384879
1184 43841547845541059 36244846780769173 33427443739970629 878556264995809 76994486248080811
1198 55350776431903243 44636444161492069 41168456550880699 1076118090058721 96828169851611431
1220 80873624627234849 61762721774419597 56967948303670597 1476570247684391 138438583845937993
1224 203986478517455989 65498138953722001 60414126919675943 1563512627260603 147684383412123709
1248 218034721194214273 92972568323121581 85762465972186313 2199581401908697 217192209790687661
1272 305405826521087869 131518908107727211 121328933827900549 3084324298546307 318237123209547251
1328 352521223451364323 291674343722717359 269126279020633673 6705700071619691 765388373532143177
1356 401429925999153707 431569653243712519 398245563152317403 9826952680681271 1178781516025065803
1370 418032645936712127 524146236967930747 483697555003575053 11878554740962309 1460437150149590411
1442 804212830686677669 1401858754603246729 1294011588320128427 31028269155282829 4322012629290955987
=======================================================================================================
**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
- 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 10^15 and
5*10^16," 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-2007).
- 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.