New largest known prime gap


Document created 18 December 2012

We (Michiel Jansen and Jens Kruse Andersen) have found the largest known prime gap with identified ends:
A gap of 3311852 from 226007#/2310-2305218 to 226007#/2310+1006634. The previous record was a gap of 2254930.
n# (called n primorial) is the product of all primes ≤ n. The form increased the chance of a large gap compared to random numbers.

A C program using the GMP (GNU Multiple Precision) library sieved for factors below 10^12. Prp testing of the 20226 remaining numbers was performed by the program PrimeForm/GW.

The prime number theorem says the "typical" gap between primes around p is approximately the natural logarithm of p. This is 225545 for our 97953-digit numbers, so the gap is 14.68 times larger than typical. The factor 14.68 is called the merit of the gap. Our goal was a record gap with merit above 10 as required by the Top-20 Prime Gaps. We believe that regardless of merit, there is no larger known prime gap with identified probabilistic or proven primes as gap ends. There are known ways to construct intervals which are part of arbitrarily large prime gaps, for example n#+2 to n#+n, but finding the gap ends for numbers of the needed size would be far harder than our search, and would rarely give a merit above 10.

Sieving was done in November 2012 on a Core 2 Duo E6600. The factors below 226007 are easy to reproduce. The factors from 226007 to 10^12 are in megagap3factors.zip. Prp tests were made November-December on a Core i7-2600. The record gap was found in the second tried interval. PrimeForm/GW made a Fermat 3-prp test on each unfactored number. The 64-bit residues are in megagap3residues.zip.

The only practical way to fully verify a prime gap is prp testing each unfactored number.
PrimeForm/GW is the fastest program for prp'ing large numbers with no special form. A much slower prp program like a GMP function would mean a software independent verification of the gap would take longer than the whole original discovery. Only every 20th of the numbers without a known factor have been double checked. That was also with PrimeForm/GW, but on independent hardware (the computer used for sieving) and with the -a1 parameter which uses a larger FFT size. This is slower but gives a different and safer calculation. All residues from the independent run were compared to the original test and they all matched. We have found no signs of problems with the used software and hardware.

The prp gap ends have passed several prp tests including Fermat tests to different bases and these:

C:>pfgw32 -a2 -tc -q226007#/2310-2305218
PFGW Version 3.6.7.32BIT.20121129.Win_Dev [GWNUM 27.8]

Primality testing 226007#/2310-2305218 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Running N+1 test using discriminant 7, base 2+sqrt(7)
226007#/2310-2305218 is Fermat and Lucas PRP! (5943.8569s+0.3097s)

C:>pfgw32 -a2 -tc -q226007#/2310+1006634
PFGW Version 3.6.7.32BIT.20121129.Win_Dev [GWNUM 27.8]

Primality testing 226007#/2310+1006634 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
Running N-1 test using base 7
Running N-1 test using base 11
Running N+1 test using discriminant 23, base 2+sqrt(23)
226007#/2310+1006634 is Fermat and Lucas PRP! (8157.5298s+0.5032s)
No attempt to prove primality has been made because it is infeasible with current computers and methods. Special forms like k*2^n+1 or k*n#+1 can be proved prime but it would be far harder to find a large prime gap where both ends are of such forms. In the very unlikely event that the supposed gap ends should be composite, there would be an even larger prime gap. For these reasons, all sites registering large prime gaps allow prp's.

Links about prime gaps:
Thomas R. Nicely's First occurrence prime gaps: http://www.trnicely.net/gaps/gaplist.html
    and http://www.trnicely.net/gaps/gaps2.html#HugeGaps
Jens Kruse Andersen's
    The Top-20 Prime Gaps: http://primerecords.dk/primegaps/gaps20.htm
    First known prime megagap: http://primerecords.dk/primegaps/megagap.htm
    Largest known prime gap: http://primerecords.dk/primegaps/megagap2.htm
Chris Caldwell's Prime Pages, The Gaps Between Primes: http://primes.utm.edu/notes/gaps.html
Eric Weisstein's Mathworld, Prime Gaps: http://mathworld.wolfram.com/PrimeGaps.html

This page was last updated 8 March  2013.
E-mail any comments.        Home