A proven prime gap of 337446

Document created April 14 2005

October 2004 Torbj÷rn Alm and Jens Kruse Andersen found a prime gap of 337446 between 7996-digit prp's (probable primes). 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 gap was originally announced without primality proofs of the gap ends p1 = 1009461925.....1170696317 and p2 = p1 + 337446. On Alm and Andersen's suggestion they were later kindly proved prime by Franšois Morain with his fastECPP (elliptic curve primality proving) in March and April 2005 (announcement).
Proving p1 took 75 days of cumulated CPU time on a Xeon 2.6GHz. p2 took 65 days. The primality certificates of p1 (6.7 MB gz file) and p2 (7.0 MB) are available. At the time they were the 9th and 10th largest ECPP proofs.

It is conjectured there are infinitely many prime gaps of all even sizes. However it has never been proven a specific gap size exists without finding an occurrence. 337446 became the largest specific gap known to exist, although there are obviously arbitrarily large prime gaps.

The prime number theorem says the average size of prime gaps near p is around log p. The merit of a gap from p1 to p2 is defined as (p2-p1) / log p1. This gap has merit 18.33 which means it is around 18.33 times larger than average. It is the largest known gap with merit above 14.70.
Rough heuristics indicate 1 of e18.33 = 91 million random gaps should have merit above 18.33, but the gap was far from random. It was found with the same method and program as the largest known prime gap between unproven prp's. This method gives numbers with no simple expression.

It has been verified with independent software and hardware that all numbers between p1 and p2 are composite. Factors found using GMP were checked with the Miracl library. Residues from Fermat 3-prp tests by PrimeForm/GW and GMP on Intel P4 and AMD Athlon XP processors were compared with a perfect match.

The previous proven gap record was by Jose Luis Gomez Pardo who found a gap of 233822 between 5878-digit primes, proved by Marcel Martin's ECPP implementation Primo. The merit is 17.28.

Update: 3 January 2010 Pierre Cami reported a new proven gap record with a gap of 351526 between 7984-digit primes, proved by Primo. The merit is 19.12. The gap with probable primes had been announced 4 August 2009.

Other links:
Jens Kruse Andersen's The Top-20 Prime Gaps: http://users.cybercity.dk/~dsl522332/math/primegaps/gaps20.htm
Thomas R. Nicely's First occurrence prime gaps: http://www.trnicely.net/gaps/gaplist.html
and http://www.trnicely.net/gaps/gaps2.html#HugeGaps
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 made by Jens Kruse Andersen. Last updated 19 December 2012.
E-mail me with any comments.        Home