Problems & Puzzles: Problems

Problem 46 . Holes and Crowds-I

As we run up over the integer numbers we may find large regions primes-free ( holes ) or its contrary, particular regions were primes are as close as they can be (crowds) according to divisibility rules.

Holes are more technically named as gaps; while crowds are better described as prime-constellations or - if we add details as how many primes are in the considered constellation -  as k-tuples.

The traditional holes (gaps) record-keeper pages are these maintained by Thomas R. Nicely and by Paul Leyland; while for crowds (k-tuples) the best place I know is the Tony Forbes's one.

Let's talk in this Problem first about holes (gaps). What is a large hole?

There are two kind of answers:

a) a large hole as an absolute large hole or simply the distance between two successive primes: (p2-p1)

b) a large hole as a relative large hole respect to the expected size of the holes in the region we are talking about: (p2-p1)/ln(p2). It happens that the expected size of a hole in the neighborhood of p2 is ln(p2), so...

Precisely Paul Leyland, in the page linked above, keeps the 20 top largest holes measured in both tastes: absolute and relative. As a matter of fact the current (June 2003) hole-records are from JosÚ Luis Pardo (20/20) and from Bertil Nyman (15/20), respectively :

Hole type Author/Date Rank Abs. Size Rel. Size p2
= (p2-p1)
JosÚ Luis Gˇmez Pardo/Set. 9, 2002 1 233833 17.28 5878 digits
JosÚ Luis Gˇmez Pardo/Apr. 13,2002 20 117930 11.04 4639 digits
= (p2-p1)/ln(p2)
Bertil Nyman/Oct. 5, 2001 1 1132 32.28 1693182318747503
Bertil Nyman/Oct. 5, 2001 20 1044 28.60 7123663452897877

As you can see we, are dealing with recent records produced, let's say, just the day before.

One more word must be said before the questions. The absolute hole-records asked are the earlier non-trivial known holes, that is to say, not the known trivial holes associated to the upper region to each n!+1 value.

Q1. Can you produce one record appropriate for each of the Top 20 Leyland's Tables (*)?

Q2. Do you devise a smart approach to beat these records (some rules to select and/or work the regions in order to seek for holes-size-records)?

I don't want to spoil the nice optimistic and fresh expression of D. H. Lehmer that goes like this "Happiness is just around the corner", said about factoring methods and targets. I just want you to have a small glimpse of the order of magnitude of the records asked to break:

1) How many digits has the number after which we get the trivial gap 233833; that is to say how many digits has 233833!+1? I will save you the calculations (Stirling's formula courtesy), but this number has something more than a million of digits, and the relative size of a gap like this, supposing primes at the extremes of this gap, would be something like 0.1 (against the 17.28 of the Gomez Pardo's record)

2) Probably you remember the result gotten by J. K. Andersen last week for the Puzzle 223. He found a remarkable gap between the primes p1=2^10093-80445 and p2= 2^10093+4185. This is a gap of absolute size, p2-p1= 84630 < 117930 and relative size (p2-p1)/ln(p2) = 84630/ln(2^10093+4185) = 84630/6996 = 12.09 <28.60. As you can see this remarkable gap can not displace the smallest (the 20th) record consigned in each of the two Tables.

So, the corner of the happiness that D. H. Lehmer mention, for sure exists, but to my conviction, this corner should be near of fast computing machines and smart approaches (the least that I can say is that happiness was not around the corner of my home this week, because I couldn't get, after two heart-selections and two overnights, any interesting result for any of the two Tables  :-)

After said all that, let's come the talent, the surprises and the happiness of all of you.

[Next week I will post another problem related to the crowds.]

(*) Leyland states 3 conditions in order to consider a record to enter in his Tables: 1) (p2-1p1)>1000, 2) p1 & p2 "must have undergone at least 5 Miller-Rabin tests for compositeness, with randomly chosen bases, and failed all five.  Note that proven primes satisfy this requirement, as do so-called PRPs" 3) (p2-p1)/ln(p2) must be not less than 10.0

J. K. Andersen sent (March, 3, 2004) the following interesting records:

Q1. Together with Hans Rosenthal and Torbj÷rn Alm running my program, I have found all the top-20 prime gaps by absolute size, with prp'ing by PrimeForm/GW. The largest by Rosenthal and I has absolute size 1001548, relative size 10.0157, and is the first known prime megagap:

The gap ends are 43429-digit probable primes with no simple expression.

My earlier gap size 84630 after p1=2^10093-80445 is still the largest known with a simple expression.

Alm and I have found the currently 9th and 10th largest relative size prime gap with prp'ing by the GMP library. The best has absolute size 7868 and relative size 30.0400 between two 114-digit proven primes: p2 = p1+7868, where p1= 561192545511605501847804031458486579170180721885050519341\


All gaps with larger relative size only have 16 or 17 digits.

We have also found around 20000 (twenty thousand) records for Thomas R. Nicely's site.

Q2 The main strategy of my program is briefly explained at

The most important part is using modular equations to select which numbers in a tested interval are divisible by each small prime, to limit the "overlap" when several small primes divide the same number.


J. K. Andersen wrote (4/6/04):

Hans Rosenthal and I have more than doubled our own record by finding a prime gap of size 2254930 between two prp's with 86853 digits:


One more new from J.K.A:

Torbj÷rn Alm, Jens Kruse Andersen and Franšois Morain have found the largest known prime gap with proven primes as end points:

The gap is 337446 between 7996-digit primes.



Robert Smith wrote (2016-09-16)

The records on this page looks somewhat out of date. There has been a major effort to find gaps between primes of all lengths since your last update.
As of today, the largest gap in terms of absolute size is the one that follows the 216,849 digit 281*499979#/46410 - 2702372. The gap is 5,103,138 in length and was found by myself. The largest gap is in the process of being double checked. The largest gap in terms of "merit" or "relative size" follows the 127 digit 7910896513*283#/30 - 6480, with merit 36.86 found by Dana Jacobsen. Both of these records were set in 2016. 
The search for larger gaps in both thew absolute sense and by merit continues, as well as extending the number of gap lengths where there is  known gap. As of the time of writing there are only 5 values of possible gap length of <100,000 still to be found. 
More details of the searches are to be found at
Dr Nicely still maintains the official prime gap records site at

Thank you Robert!




Records   |  Conjectures  |  Problems  |  Puzzles