Thomas R. Nicely

Current e-mail address

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.

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

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.

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.

Table 1. First occurrence prime gaps in 1e15 < p < 3e15. ============================================================= Gap Following the Gap Following the prime prime ============================================================= 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 ============================================================= *Maximal gap.

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 Jansen's gap.

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.

- 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 RMT 55.
- 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, MR 81g:10002.
- Kenneth Conrow, gap data files available (11 April 2003) at ftp://unix.ksu.edu/pub/pentadecet/npgfile.sav.
- 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), MR 2002c:11174.
- 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, 171-176.
- 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), UBASIC, 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 zipfile at this site. See also http://www.rkmath.rikkyo.ac.jp/~kida/ubasic.htm.
- 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 http://www.trnicely.net/twins/twins.html
- 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 http://www.trnicely.net/gaps/gaps.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). 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.
- 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 http://www.ift.uni.wroc.pl/~mwolf.
- Jeff Young and Aaron Potler, "First occurrence prime gaps," Math. Comp. 52:185 (1989) 221-224, MR 89f:11019.

- A comprehensive and updated listing of all presently known first occurrence and maximal prime gaps, including recent results obtained by Professor Tomás Oliveira e Silva and colleagues, of the Universidade de Aveiro, Portugal, Professor Siegfried "Zig" Herzog of Penn State University (Mont Alto), 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.
- 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 Andersen's website,
- 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 PRIMO. Additional details are available at Andersen's website. - 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) athttp://www.tex.ac.uk/tex-archive/systems/msdos/.

- Top of page
- "New prime gaps between 1e15 and 5e16"
- "New maximal prime gaps and first occurrences"
- Listing of all known first occurrence and maximal prime gaps
- Tables of first known occurrence prime gaps
- Home page