First occurrence of a prime gap of 1000 or greater

Thomas R. Nicely

http://www.trnicely.net
Current e-mail address

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.

Abstract

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)

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

Key Words and Phrases

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

1. Introduction

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

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. 

  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.

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 http://www.trnicely.net/gaps/gaplist.html. See also the addendum to this paper.

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

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.

5. Acknowledgments

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.

References

Addendum

NOTE: This addendum was not part of the original submission for publication.