Largest known prime gap


Document created May 31 2004

January 2004 we (Hans Rosenthal and Jens Kruse Andersen) found the first known prime megagap with size 1001548.
January-May 2004 we found a new record prime gap with size 2254930 between two probabilistic primes (prp's) with 86853 digits. Sieving for small factors used the GMP (GNU Multiple Precision) library. Prp testing of the remaining numbers was performed by the program PrimeForm/GW.

The prime number theorem says the "typical" gap between primes around p is close to the natural logarithm of p. This is 199984 here, so the gap is 11.28 times larger than typical. That satisfied our goal which was finding a gap above 2 million, and at least 10 times the typical as required by the Top-20 Prime Gaps.
We also believe that regardless of relative size, there is no larger known prime gap with identified probabilistic or proven primes as gap ends. n!+2 to n!+n can be part of an arbitrarily large prime gap, but finding the gap ends for a gap above 2 million would be far harder than our search.

The bounding primes were found on the form:
p1 = 273489*m+c-93554 and p2 = p1 + 2254930 = 273489*m+c+2161376
where m and c are 86847-digit numbers with no simple expression.
m is the product of many but not all primes <= 319567.
c was chosen modulo all 18015 prime factors of m, to ensure unusually many numbers (1994349) with one of those prime factors in an interval of 2 million following k*m+c for any k. The found gap with k=273489 exceeds this interval at both ends.
Decimal expansions of m, c and p1 are in a zipped text file, and p1 also in p1.txt.
k was chosen after 1 million intervals were sieved to 100 million and some of these to 250 billion, to ensure a factor was found for more than average of the 5651 remaining unfactored numbers in the 2 million interval. 3230 of the 5651 numbers were factored for the record gap. All found factors above 1 billion, including those outside the 2 million interval, are in megagap2factors.zip. They have been verified by independent software and hardware.

A few days were first used to find good values for m and c. The total time for sieving and prp'ing was then around 3.5 months (not counting 2 interruptions) from January 27 to May 26 2004 on a single 3.06 GHz Pentium 4. The gap was found in the first tried interval with k=273489, so the only prp's computed were the 2 gap ends. A Fermat 3-prp test was performed on each unfactored number by PrimeForm/GW. The prp test residues are in megagap2residues.zip. Only 2421 prp tests were necessary inside the 2 million interval where 2421/2000000 = 0.12% of the numbers were unfactored. As consequence of an apparent feature of the algorithm to find c, the first 34305 and last 69603 numbers inside this interval were all factored. 7040 additional prp tests were required outside to find the gap ends.

The only practical way to verify a prime gap is prp testing each unfactored number.
There is apparantly no program as fast as PrimeForm/GW 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 several times longer than the whole original discovery. Only 50 random of the intermediate composites without a known factor have been verified. That was also with PrimeForm/GW but on independent hardware. 3-prp test residues on an Athlon XP were compared to the original Pentium 4 test and all matched.

The gap ends have been prp tested by the independent GMP library on an Athlon XP cpu. A Fermat 210-prp and 5 Miller-Rabin tests were performed. Numerous additional prp tests including Fermat tests to all prime bases below 256 were made with PrimeForm/GW on a Pentium 4.
No attempt to prove primality has been made since it is far beyond current computers and methods for numbers with no special form. Special forms like k*2^n+1 can be proved prime but it would be far harder to find a large prime gap for such forms. In the extremely 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.

This prime gap record has later been improved by Michiel Jansen and Jens Kruse Andersen to 3311852: New largest known prime gap

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://users.cybercity.dk/~dsl522332/math/primegaps/gaps20.htm
    First known prime megagap: http://users.cybercity.dk/~dsl522332/math/primegaps/megagap.htm
    New largest known prime gap: http://users.cybercity.dk/~dsl522332/math/primegaps/megagap3.htm
Jens Kruse Andersen's The Top-20 Prime Gaps: http://users.cybercity.dk/~dsl522332/math/primegaps/gaps20.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
Official announcement of this gap, A prime gap of 2254930: NMBRTHRY archives

Some text files were made by Hans Rosenthal.
This page was made by Jens Kruse Andersen and last updated 19 December 2012.
E-mail me with any comments.        Home