First occurrence of a prime gap of 1000 or greater
Thomas R. Nicely
Dr. Bertil Nyman
Freeware copyright (C) 2015 Thomas R. Nicely and Bertil Nyman. Nicely
has released his contributions into the public domain, but disclaims
any legal liability arising from their use.
Last modified 2230 GMT 29 May 2015.
Date of first release 21 May 1999.
The content of this document (other than the addendum, which was
not part of the submission for publication) is essentially that of
the original release, except that information rendered obsolete or
incomplete by subsequent developments has been removed or modified,
in both the main document and the addendum. This liberty is taken
in view of the fact that the paper was never accepted for
publication. There may also be differences in formatting, and in
minor details and corrections.
The interval from 1e15 to 3e15 is analyzed for first
occurrence prime gaps and maximal prime gaps. Thirty-four new
first occurrences are found, including three new maximal gaps.
The first occurrence of a prime gap of 1000 or greater is found
to be the maximal gap of 1132 following the prime 1693182318746371.
Mathematics Subject Classification 2000 (MSC2000)
Secondary: 11-04, 11Y11, 11Y99.
Key Words and Phrases
Prime numbers, prime gaps, first occurrences, maximal gaps, maximal
prime gaps, kilogap.
A prime gap is the difference between successive primes; it constitutes
a first occurrence when no preceding gap has an equal value. A first
occurrence prime gap is maximal if the gap strictly exceeds all preceding
The search for first occurrence and maximal prime gaps has been
successively extended to 1e15 by the works of Glaisher (1877),
Western (1934), Lehmer (1957), Gruenberger, Armerding, and
Baker (1959, 1961), Appel and Rosser (1961), Lander and Parkin (1967),
Brent (1973, 1980), Young and Potler (1989), and Nicely (1999).
The present work extends this upper bound to 3e15.
2. Computational Technique
The authors worked to a large degree along independent lines.
Nicely began his tabulation of prime gaps in August 1995,
proceeding from 7.2e13, just below the level
previously published by Young and Potler (1989). This search was added
in process (at the suggestion of Jörg Richstein, Universität
Giessen, Germany) to a larger project (Nicely, 1995) which had been
running continuously since 1993. The calculations were distributed
among several (the number varied from a few to more than two dozen)
personal computers, most of them equipped with Pentium processors
running 32-bit C code in an extended DOS environment. All
calculations were duplicated on separate machines in order to guard
against system errors, particularly memory faults, of which
approximately thirty have thus far been observed. The algorithm was
based on the sieve of Eratosthenes, exhaustively scanning successive
and contiguous blocks of odd integers for primes, prime gaps, prime
constellations, and the reciprocal sums of the constellations in both
long double (19 significant digits) and ultraprecision (53 decimal
places) floating point. A small (~ 2.5MB) byte array was initialized
with the gaps preceding the square root of the upper limit of the run;
these gaps were computed from the values of the primes less than
96000000, retrieved from a disk file in which they were stored in bit
form, thirty integers to a byte. The byte array of gaps was then used
repeatedly during execution to calculate the sieving primes for trial
division. The block of integers to be sieved was stored in a large
array, limited only by available physical memory, one odd integer per
byte, its value equal to the base value of the block plus twice the
byte offset. Single-system throughput peaked at 5.6 million integers
per second, using a 233 MHz Pentium MMX CPU and 64MB of RAM.
Results to 1e15 were completed in October 1997 and
presented in (Nicely, 1999). Between October 1997 and February 1999
these calculations were extended in a similar fashion to 1.6e15.
Meanwhile, in August 1998, Nyman independently began writing similar
code, initiating that October a scan of selected regions between
1.8e15 and 3e15, searching for prime gaps whose first
occurrences were still unknown. Nyman employed several Pentium II
systems running C++ Win32 code under Windows NT. Nyman's algorithm
was similar to Nicely's, but without the floating point code and prime
constellations analysis. Nyman used a bit array for the block of
integers to be sieved, thus storing sixteen integers per byte, and
avoided sieving with the small primes < 23 by utilizing
appropriately initialized memory blocks whose sizes were multiples of
3*5*7*11*13*17*19 = 4849845 bytes (Nicely used a variation
of this technique). Nyman's single-system throughput peaked at 12
million integers per second, using dual 400 MHz Pentium II CPUs (with
multithreaded code) and 512MB of RAM. Nyman soon detected a number of
new first known occurrences of prime gaps, but at the time of discovery
these were not established as first occurrences, since the regions scanned
were not contiguous to Nicely's nor, in some cases, to each other. Nyman
initiated an e-mail exchange of results with Nicely, and on 24 January
1999 reported a gap of 1132 following the prime 1693182318746371.
This gap was of great significance, the first known occurrence of a gap
of 1000 or greater---a "kilogap." Nyman then agreed to scan
the remaining missing regions between Nicely's February target point of
1.6e15 and the location of the kilogap. By 18 February 1999 all
prime gaps preceding the 1132 gap had been checked, demonstrating that
this gap was indeed a maximal gap and the first occurrence of any gap of
1000 or greater. By 15 May 1999 Nyman had extended the upper bound of
exhaustive analysis to 3e15 meanwhile, Nicely had independently
checked Nyman's computations through 1.722e15, confirming the gap
of 1132 as the first kilogap.
3. Computational Results
Table 1 presents the new first occurrence prime gaps found between
1e15 and 3e15; maximal gaps are indicated by an asterisk (*).
The gaps to 1.58e15 were first reported by Nicely; the remainder
were discovered by Nyman.
Listings of previously known first occurrence prime gaps can
be found in (Young and Potler, 1989) and in (Nicely, 1999),
and are herein omitted for brevity. A comprehensive and updated
listing of first occurrence and maximal prime gaps is available at
See also the addendum to this paper.
Table 1. First occurrence prime gaps in 1e15 < p < 3e15.
Gap Following the Gap Following the
796 1271309838631957 876 1125406185245561
812 1710270958551941 878 2705074880971613
824 1330854031506047 884 1385684246418833
838 1384201395984013 888 2389167248757889
842 1142191569235289 892 2606748800671237
846 1045130023589621 894 2508853349189969
848 2537070652896083 900 2069461000669981
850 2441387599467679 902 1555616198548067
852 1432204101894959 908 2126985673135679
854 1361832741886937 910 1744027311944761
856 1392892713537313 912 2819939997576017
858 1464551007952943 916* 1189459969825483
864 2298355839009413 918 2406868929767921
866 2759317684446707 924* 1686994940955803
868 1420178764273021 936 2053649128145117
870 1598729274799313 990 2764496039544377
874 1466977528790023 1132* 1693182318746371
4. Comments Regarding the 1132 Gap
The authors found the discovery of the maximal gap of 1132
quite surprising. The preceding maximal gap was the one of 924;
thus the 1132 gap represents a jump of 208 in absolute magnitude
and 22.5 % in relative magnitude. This is by far the largest
increase observed in absolute magnitude, the previous maximum being
the increase from 806 to 906 recorded by Nicely (1999). The increase
in relative magnitude is the largest observed since the increase
from a gap of 52 following the prime 19609 to the gap of 72
following the prime 31397, as detected by J. W. L. Glaisher (1877) and
noted by A. E. Western (1934) with the aid of Mrs. E. Gifford, at a
point nearly eleven orders of magnitude earlier among the positive
Below 3e15, only twenty gaps of 900 or greater have been observed;
the 1132 gap is the only one of these exceeding 990.
The gap of 1132 is also of significance to the related conjectures
put forth by Cramér (1936) and Shanks (1964), concerning the
ratio R_csg=g/ln²(p_1). Shanks reasoned that its limit, taken over all
first occurrences, should be 1; Cramér argued that the limit superior,
taken over all prime gaps, should be 1. Granville (1994), however,
provides evidence that the limit superior is >= 2*exp(-gamma) = 1.1229.
For Nyman's 1132 gap, R_csg=0.9206386, the largest value observed for any
p_1 > 7 (note that if the Cramér-Shanks-Granville ratio is defined
instead as g/ln²(p_2), the gaps following 2, 3, and 7 no longer
require exclusion as exceptional cases). The largest maximal gap
presently known was discovered (circa 01 April 2009) by Professor
Tomás Oliveira e Silva,
Universidade de Aveiro, Portugal---a gap of 1476 following the prime
1425172824437699411. Silva's gap of 1476 exhibits the greatest merit
(35.310308) of any maximal gap presently known; however, R_csg=0.8447275,
still less than that of Nyman's 1132 gap. Michiel Jansen has since
discovered (03 January 2012) a first known occurrence prime gap of even
greater merit (a gap of 66520, merit 35.4244594, following the prime
1931*1933#/7230 - 30244); however, R_csg is only 0.0188648876 for
Several models have been conjectured for the distribution of
prime gaps, including those of Western (1934), Cramér (1936),
Shanks (1964), Wolf (1997), and Rodriguez (1999). Refer to the
online published addendum to
(Nicely, 1999) for a detailed discussion; here we note only that
most of the models yield predicted locations exceeding 1e16 for
the 1132 gap, further emphasizing the unexpectedness of its appearance.
Nicely expresses his appreciation to two colleagues, Glenn
Berman and Dr. Harel Barzilai, for their assistance with TeX and
LaTeX. Dr. Nyman wishes to thank SaabTech Systems AB (formerly
CelsiusTech Systems AB) for providing excellent computing facilities.
- Kenneth I. Appel and J. Barkley Rosser, "Table for estimating
functions of primes," Communications Research Division Technical
Report Number 4, Institute for Defense Analyses, Princeton NJ (1961),
xxxii + 125 pp. (22 cm.). Reviewed in Math. Comp. 16:80 (1962) 500-501
- C. L. Baker and F. J. Gruenberger, "The first six million prime
numbers," The Rand Corporation, Santa Monica CA, published by the
Microcard Foundation, Madison WI (1959), 8 pp. (16x23 cm.) + 62
cards (7.5x12.6 cm). Reviewed in Math. Comp. 15:73 (1961) 82 RMT 4.
- 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-36,
- Kenneth Conrow, gap data files available (11 April 2003) at
- Harald Cramér, "On the order of magnitude of the
difference between consecutive prime numbers," Acta Arith.
2 (1936) 23-46.
- Pamela A. Cutter, "Finding prime pairs with particular
gaps," Math. Comp. 70:236 (2001) 1737-1744 (electronic),
- Harvey Dubner, e-mail communication (04 August 1996).
- J. W. L. Glaisher, "On long successions of composite
numbers," Messenger of Mathematics 7 (1877) 102-106,
- Andrew Granville, "Unexpected irregularities in the
distribution of prime numbers," in Proceedings of the
International Congress of Mathematicians, Vol. I (Zürich, 1994),
Birkhäuser, Basel, 1995, pp. 388-399. MR 97d:11139.
- F. J. Gruenberger and G. Armerding, "Statistics on the first six
million prime numbers," Paper P-2460 of the Rand Corporation,
Santa Monica CA (1961), 145 pp. (8.5" x 11"). Reviewed in Math. Comp.
19:91 (1965) 503-505 RMT 73.
- Yûji Kida (Professor of Mathematics, Rikkyo University, Japan),
a freeware ultraprecision programming, development, and runtime
environment with number theoretical enhancements. Version 8.8f
(08 October 2000) is provided (05 August 2008) as a
at this site. See also
- L. J. Lander and T. R. Parkin, "On the first appearance of
prime differences," Math. Comp. 21 (1967) 483-488, MR 37#6237.
- Derrick Henry Lehmer, "Tables concerning the distribution
of primes up to 37 millions," 1957. Copy deposited
in the UMT file and reviewed in MTAC 13 (1959) 56-57.
- Thomas R. Nicely, "Enumeration to 1e14 of the twin primes
and Brun's constant," Virginia Journal of Science 46:3 (Fall,
1995) 195-204, MR 1401560 (97e:11014). Electronic reprint available at
- Thomas R. Nicely, "New maximal prime gaps and first
occurrences", Math. Comp. 68:227 (July, 1999) 1311-1315,
MR 1627813 (99i:11004). Electronic reprint available at
- 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). Available in various formats (PS, PDF,
dvi, AMS-LaTeX2e) at the home page of the
- Luis Rodriguez (AKA Luis Rodriguez Abreu/Torres), e-mail
communication (15/18 January 1999); also noted (17 January 2002) at
- Daniel Shanks, "On maximal gaps between successive
primes," Math. Comp. 18 (1964) 646-651, MR 29#4745.
- A. E. Western, "Note on the magnitude of the
difference between successive primes," J. London Math. Soc.
9 (1934) 276-278.
- Marek Wolf, "First occurrence of a given gap between
consecutive primes", preprint (April, 1997), available
(May, 1999) at
- Jeff Young and Aaron Potler, "First occurrence prime
gaps," Math. Comp. 52:185 (1989) 221-224, MR 89f:11019.
NOTE: This addendum was not part of the original submission for
- A comprehensive and updated listing of all presently known
first occurrence and maximal prime gaps, including recent
results obtained by
Tomás Oliveira e Silva and colleagues, of the
Universidade de Aveiro, Portugal,
"Zig" Herzog of Penn State University (Mont Alto),
is available at
In addition, extensive tables of
first known occurrence prime gaps are available at this site.
- The largest known specific prime gap is one of measure 3311852 (merit
14.683768), discovered by Michiel Jansen and Jens Kruse Andersen
(announced 18 December 2012). They have confirmed the bounding primes
(97953 digits each) probabilistically; no attempt to certify them
deterministically is presently anticipated. Details are available at
- The largest prime gap whose bounding primes have been certified
deterministically is a gap of 1113106 (merit 25.904452) following the
prime 587*43103#/2310 - 455704. The gap was discovered
(and confirmed probabilistically) by Jens Kruse Andersen, Michiel
Jansen, and Pierre Cami on 8 March 2013. The discoverers completed the
deterministic certification of the end-point primes (18662 digits each)
on 29 October 2013, using Marcel Martin's implementation of ECPP in
Additional details are available at
- The gaps of Andersen, Jansen, and Cami are among many large
prime gaps tabulated by Jens Kruse Andersen on his page
The Top-20 Prime Gaps, a compilation maintained prior to
February 2004 by Paul Leyland. See also the
tables of first known occurrence
prime gaps at this site.
- The authors wish to express their appreciation to Eberhard
Mattes for his outstanding free software package emTeX, an
implementation of TeX and LaTeX2e for extended DOS and OS/2.
The emTeX package is available on the
TeX Users Group TeX Live 4
CD, or (as of July, 1999) at