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://primerecords.dk/primegaps/gaps20.htm

First known prime megagap:
http://primerecords.dk/primegaps/megagap.htm

New largest known prime gap: http://primerecords.dk/primegaps/megagap3.htm

Jens Kruse Andersen's The Top-20 Prime Gaps:
http://primerecords.dk/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