# First known prime megagap

Document created January 12 2004

January 2004 we (Hans Rosenthal and Jens Kruse Andersen) found a prime gap of 1001548 between two probabilistic primes (prp's) with 43429 digits. Sieving for small factors used the GMP multiple precision library, and prp testing of the remaining numbers was performed by the program PrimeForm/GW.

The logarithm of the primes is 99997 so the gap is 10.02 times the "typical" gap by the prime number theorem. This just satisfied our goal which was finding a megagap (gap>10^6) meeting the requirements of Paul Leyland's Top-20 Prime Gaps.
We also think 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 clearly be part of an arbitrarily large prime gap.

n# is the product of all primes <= n. The bounding primes were found on the form p1 = 279893*100343#+c-81498 and p2 = p1+1001548, where c is a 43423-digit number with no simple expression. c was chosen modulo all primes up to 100343, to ensure unusually many numbers (994427) with a factor <= 100343 in an interval of 10^6 following k*100343#+c for any k. The found gap and that interval do not line up completely but that could not have been expected.
Decimal expansions of c and p1 are in a text file.
k was chosen after sieving of 1 million intervals to 10^8 and some of these to 2^32, to ensure many of the 5572 remaining unfactored numbers had a factor between 100343 and 2^32.
The first tried interval was abandoned after the early prp 348271*100343#+c+384834. The megagap was found in the second interval. The total time including sieving was 272 hours on a 3.06 GHz Pentium 4, where only 3 prp's were computed. A Fermat 3-prp test was performed by PrimeForm/GW and the residues for the megagap are in megagapresidues.zip.

The only way to verify a prime gap seems to be prp testing each unfactored number.
We don't know of a 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 an independent verification of the gap will take much longer than the whole original discovery.
All factors have been verified on an Athlon cpu. All intermediate composites without a known factor have been verified with PrimeForm/GW on independent hardware. 3-prp test residues on an Athlon XP 3000+ were compared to the original Pentium 4 run. 9 residues did not match. Repeated testing of these, both on the same Athlon XP 3000+ and an Athlon XP 1500+, all matched the Pentium 4. We conclude the 9 mismatches were temporary errors with unknown source and all residues now have been matched successfully.

The gap ends have been independently 3-prp tested by GMP on an Athlon cpu in addition to numerous prp tests to different bases by PrimeForm/GW. No attempt to prove primality has been made since it seems far too hard with current methods and computers.
top20gaps.zip contains the submission of this and 14 other prime gaps to Paul Leyland's top-20.

This prime gap record has later been improved by us to 2254930: Largest known prime gap