New prime gaps between 1e15 and 5e16

Dr. Bertil Nyman

SaabTech Systems AB
Uppsala, Sweden

Thomas R. Nicely

(Corresponding author)
http://www.trnicely.net
Current e-mail address

Freeware copyright (C) 2017 Bertil Nyman and Thomas R. Nicely. Nicely has released his contributions into the public domain, but disclaims any legal liability arising from their use.

Document History 

Last modified..............0800 GMT 12 July 2017.
Journal citation...........Journal of Integer Sequences 6 (2003), Nummber 3, Article 03.3.1, pp. 1-6 (electronic).
Mathematical Reviews.......MR1997838 (2004e:11143).
Publication date...........13 August 2003.
Accepted for publication...13 August 2003.
Revision submitted.........13 August 2003.
Original submission........10 February 2003.

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. The journal article is available in various formats (PS, PDF, dvi, AMS-LaTeX2e) at the Journal of Integer Sequences.

Abstract

The interval from 1e15 to 5e16 was searched for first occurrence prime gaps and maximal prime gaps. One hundred and twenty-two new first occurrences were found, including four new maximal gaps, leaving 1048 as the smallest gap whose first occurrence remains uncertain. The first occurrence of any prime gap of 1000 or greater was found to be the maximal gap of 1132 following the prime 1693182318746371. A maximal gap of 1184 follows the prime 43841547845541059. More extensive tables of prime gaps are maintained at http://www.trnicely.net.

Mathematics Subject Classification 2000 (MSC2000)

Primary: 11A41.
Secondary: 11-04, 11Y55.

Key Words and Phrases

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

1. Introduction

We restrict our discussion to the positive integers. Let Q denote the sequence of prime numbers, Q = {2,3,5,7,11,...,q_k,q_(k+1),...}, and D the sequence of differences of consecutive prime numbers, D = {1,2,2,4,...,q_(k+1)-q_k,...}.

A prime gap G is the interval bounded by two consecutive prime numbers q_k and q_(k+1). The measure (size, magnitude) g of a prime gap G is the difference g=q_(k+1)-q_k of its bounding primes. A prime gap is often specified by its measure g and its initial prime p_1=q_k, and less often by the measure g and the terminal prime p_2=q_(k+1). A prime gap of measure g contains g-1 consecutive composite integers. The measures of the prime gaps are the successive elements of the sequence D. Since two is the only even prime, every prime gap is of even measure, with the sole exception of the prime gap of measure 1 following the prime 2.

In illustration, a gap of measure g=6 (or simply a gap of 6) follows the prime p_1=23, while a gap of 10 follows the prime 139.

It is elementary that gaps of arbitrarily large measure exist, since, as observed by Lucas (1891), for n > 0 the integer (n+1)! + 1 must be followed by at least n consecutive composites, divisible successively by 2,3,...,n+1; however, n+1 represents only a lower bound on the measure of such gaps.

The merit M of a prime gap of measure g following the prime p_1 is defined as M=g/ln(p_1). It is the ratio of the measure of the gap to the "average" measure of gaps near that point; as a consequence of the Prime Number Theorem, the average difference between consecutive primes near x is approximately ln(x).

A prime gap of measure g is considered a first occurrence prime gap when no smaller consecutive primes differ by exactly g, i.e., when this is the first appearance of the positive integer g in the sequence D. Thus, the gap of 4 following 7 is a first occurrence, while the gap of 4 following 13 is not. Note that this usage of the compound adjective first occurrence carries no implication whatsoever regarding historical precedence of discovery. Multiple instances of gaps of 1048 are known, but none is yet known to be a first occurrence, even though one of them bears an earliest historical date of discovery. This terminology follows that of Young and Potler (1989), and produces more concise phrasing than some past and present alternative nomenclature.

A prime gap of measure g is titled maximal if it strictly exceeds all preceding gaps, i.e., the difference between any two consecutive smaller primes is < g, so that g exceeds all preceding elements of D. Thus the gap of 6 following the prime 23 is a maximal prime gap, since each and every smaller prime is followed by a gap less than 6 in measure; but the gap of 10 following the prime 139, while a first occurrence, is not maximal, since a larger gap (the gap of 14 following the prime 113) precedes it in the sequence of integers. Maximal prime gaps are ipso facto first occurrence prime gaps as well.

Furthermore, the term first known occurrence prime gap is used to denote a prime gap of measure g which has not yet been proven to be (and may or may not be) the true first occurrence of a gap of measure g; this situation arises from an incomplete knowledge of the gaps (and primes) below the first known occurrence. Thus, Nyman discovered a gap of 1048 following the prime 88089672331629091, and no smaller instance is known; but since his exhaustive scan extended only to 5e16, this gap remains for the moment merely a first known occurrence, not a first occurrence. First known occurrences serve as upper bounds for first occurrences not yet established.

The search for first occurrence and maximal prime gaps was previously 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 5e16. The calculations are currently being continued toward 4e18, by Tomás Oliveira e Silva (2001-2012), as part of a project generating numerical evidence for the Goldbach conjecture.

2. Computational Technique

The calculations were carried out over a period of years, distributed asynchronously among numerous personal computers, taking advantage of otherwise idle CPU time. Nyman accomplished the bulk of the computations; employing as many as eighty systems from 1998 to 2002, he accounted for the survey of the region from 1.598508912e15 through 5e16. Nicely's enumerations of prime gaps began in the summer of 1995, but the portion reported here was carried out from 1997 to 1999, over the interval from 1e15 to 1.598508912e15, the number of systems in use varying from about five to twenty-five. The algorithms employed the classic sieve of Eratosthenes, with the addition of a few speed enhancing optimizations, to carry out an exhaustive generation and analysis of the differences between consecutive primes. More sophisticated techniques for locating large prime gaps, such as scanning through arithmetic progressions, were rendered impractical by the fact that the search for first occurrences was being carried out concurrently with other tasks; Nicely was enumerating prime constellations, while Nyman was gathering comprehensive statistics on the frequency distribution of prime gaps.

Among the measures taken to guard against errors (whether originating in logic, software, or hardware), the count pi(x) of primes was maintained and checked periodically against known values, such as those published by Riesel (1994), and especially the extensive values computed recently by Silva (2001-2012). In addition, Nicely has since duplicated Nyman's results through 4.5e15.

3. Computational Results

Table 1 lists the newly discovered first occurrence prime gaps resulting from the present study; maximal gaps are indicated by an asterisk (*). Each table entry shows the measure g of the gap and the initial prime p_1. The fifteen gaps between 1e15 and 1.598508912e15 are due to Nicely; all the rest were discovered by Nyman.

4. Observations

As a collateral result of his calculations, Nyman has computed for the count of twin primes the value pi_2(5e16) = 47177404870103, the maximum argument for which this function has been evaluated. Nyman also obtained pi(5e16) = 1336094767763971 for the corresponding count of primes; this is the largest value of x for which pi(x) has been determined by direct enumeration, and confirms the value previously obtained by Deléglise and Rivat (1996), using indirect sieving methods. Nyman has also generated frequency tables for the distribution of all prime gaps below 5e16.

Listings of the 423 previously known first occurrence prime gaps (including 61 maximal gaps), those below 1e15, have been published collectively by Young and Potler (1989) and Nicely (1999), and are herein omitted for brevity.

A comprehensive listing of first occurrence and maximal prime gaps, annotated with additional information, is available at Nicely's URL. Nicely also maintains at his URL extensive lists of first known occurrence prime gaps, lying beyond the present upper bound of exhaustive computation, and discovered mostly by third parties, notably Harvey Dubner (1995-2003). These lists exhibit specific gaps for every even positive integer up to 10884, as well as for other scattered even integers up to 233822; for some of the gaps exceeding 8000 in magnitude, the bounding integers have only been proved strong probable primes (based on multiple Miller's tests).

The largest gap herein established as a first occurrence is the maximal gap of 1184 following the prime 43841547845541059, discovered 31 August 2002 by Nyman. The smallest gap whose first occurrence remains uncertain is the gap of 1048.

The maximal gap of 1132 following the prime 1693182318746371, discovered 24 January 1999 by Nyman, is the first occurrence of any "kilogap," i.e., any gap of measure 1000 or greater. Its maximality persists throughout an extraordinarily large interval; the succeeding maximal gap is the gap of 1184 following the prime 43841547845541059. The ratio of the initial primes of these two successive maximal gaps is 25.89, far exceeding the previous extreme ratio of 7.20 for the maximal gaps of 34 (following 1327) and 36 (following 9551), each discovered by Glaisher (1877). Furthermore, the gap of 1132 has the greatest merit (32.28) of any known gap; the maximal gap of 1184 is the only other one below 5e16 having a merit of 30 or greater.

The gap of 1132 is also of significance to the related conjectures put forth by Cramér (1936) and Shanks (1964), concerning the ratio 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 the 1132 gap, the ratio is 0.9206, the largest value observed for any p_1 > 7, the previous best being 0.8311 for the maximal gap of 906 following the prime 218209405436543, discovered by Nicely (1999) in February, 1996.

Several models have been proposed in an attempt to describe the distribution of first occurrence prime gaps, including efforts by Western (1934), Cramér (1936), Shanks (1964), Riesel (1994), Rodriguez (1999), Silva (2001-2012), and Wolf (1997); further details are available here. We simply note here Nicely's empirical observation that all first occurrence and maximal prime gaps below 5e16 obey the following relationship:

(1) 0.122985*sqrt(g)*exp(sqrt(g)) < p_1 < 2.096*g*exp(sqrt(g)) .

The validity of (1) for all first occurrence prime gaps remains a matter of speculation. Among its corollaries would be the conjecture that every positive even integer represents the difference of some pair of consecutive primes, as well as a fairly precise estimate for the answer to the question posed in 1964 by Paul A. Carlson to Daniel Shanks (1964), to wit, the location of the first occurrence of one million consecutive composite numbers. The argument g=1000002 entered into (1) yields the result 2.4e436 < p_1 < 4.2e440, which is near the middle of Shanks' own estimate of 1e300 < p_1 < 1e600.

5. Acknowledgments

Nyman wishes to thank SaabTech Systems AB for providing excellent computing facilities.

References