Figure1. A plot of Cramer's Conjecture.
Ed Pegg Jr., January 26, 2003
Long ago, Euclid proved the infinitude of primes. Given a set of prime numbers (say, 2 3 5 7), none of the original numbers divides the product minus one (2×3×5×7-1 = 209 = 11×19). Likewise, none of the original numbers divides the product plus one (211 is prime). Assuming a finite number of primes leads to a contradiction, due to these extra primes.
Euclid's method can be used to demonstrate an arbitrarily large gap between prime numbers. An example of a prime gap of size 20 is found between primes 887 and 907. 887, 2×2×2×3×37, 7×127, 2×5×89, 3×3×3×3×11, 2×2×223, 19×47, 2×3×149, 5×179, 2×2×2×2×2×2×2×7, 3×13×23, 2×449, 29×31, 2×2×3×3×5×5, 17×53, 2×11×41, 3×7×43, 2×2×2×113, 5×181, 2×3×151, 907. Thus, {887,907} gives a prime gap. A different method for finding a prime gap of size at least 20 uses {20!+1, 20!+21}, {20!-1, 20!-21}, {20#+1, 20#+21}, or {20#-1, 20#-21}.
We know that each range will be prime-free. 20!+7, 20!-7, 20#+7, 20#-7 are all divisible by 7. 20!+8, 20!-8, 20#+8, 20#-8 are all divisible by 2. 20!+9, 20!-9, 20#+9, 20#-9 are all divisible by 3. And so on. The numbers n#+1 (A005234), n#-1 (A006794), n!+1(A002981), and n!-1 (A002982) might be prime, but usually are not.
Note that 20# is the product of all primes ≤ 20. So, 19# = 20# = 21# = 22# = 2×3×5×7×11×13×17×19 = 9699690. 20! is the product of all whole numbers ≤ 20. So, 20! = 1×2×3×4×5×6×7×8×9×10×11×12×13×14×15×16×17×18×19×20 = 2432902008176640000. While I'm on notation, n is a whole number, and p is a prime number.
All the numbers in these various ranges gives a prime gap of size 20. The range starting with 887 is considerably smaller than 9699690 or 2432902008176640000. In fact, the 887-907 gap is the first of size 20. It is a maximal primegap. With numbers of this size, the average gap is ln(887) ~ 6.78, by the prime number theorem. The merit of this gap is 20/ln(887) ~ 2.95. The higher the merit, the more interesting it is. At the moment, the highest known merit goes to p=1693182318746371. The next prime is p+1132. The merit of this gap is 1132/ln(p) ~ 32.28. It is the smallest known kilogap, and was found by Bertil Nyman in 1999. Only four other primegaps with a merit exceeding 30 are known. 1184/ln(43841547845541059) ~ 30.9 (Bertil Nynam, 2002), 1198/ln(55350776431903243) ~ 31.1 (Tomás Oliveira e Silva, 2002), 1220/ln(80873624627234849) ~ 31.3 (Tomás Oliveira e Silva, 2003), and 7868/ln(561192545511605501847804031458486579170180721885050519341523637380951060985753413015561149180502147007767345472029) ~ 30.04 (Torbjörn Alm, 2004). The first four are all maximal primegaps. Thomas R. Nicely maintains a list of first occurrence prime gaps.
In 1936, Harold Cramer conjectured that 1 > gap(p)/ ln(p)^2 for all primegaps. Figure 1 shows how Cramer's conjecture is doing as of 2004, with a plot of gap(p)/ln(p)^2 for the first 67 maximal primegaps. As you can see, the graph is approaching 1. 1132/ln(1693182318746371)^2 ~ .920639 is the high point.
Figure1. A plot of Cramer's Conjecture.
In January 2004, Jens Kruse Andersen and Hans Rosenthal found the first interesting megagap between primes with 43429 digits. The merit of this gap is 10 -- quite respectable for this territory of numbers. Unfortunately, there doesn't seem to be any simple form for this number.
A megagap. It might even be larger. The two bounding numbers are both probable primes. As the name suggests, they are probably prime. That means they passed strong primality testing (a 2-spsp test, a 3-spsp test, and a Lucas pseudoprime test). Probable primes are prime with a 99.99999999999999% certainty, and this battery of tests never fails for numbers under 10^16. No counterexamples are known. Unfortunately, it is possible that the strong primality test might fail on some number. As a cautionary tale, consider the earliest version of Mathematica, when the PrimeQ function was slightly different. PrimeQ incorrectly described the number 6646915915638769 = 7309×321553×2828197 as prime (this error was fixed a decade ago). To be absolutely 100% certain that a number exceeding ten quadrillion is prime, elliptic curve primality proving can be used. The PRIMO program is likely the best at this for numbers over a thousand digits. PRIMO certified as prime 14009# - 23899, a 6027-digit number, with 4 months of computation, and provided a proof of primality. A strong primality test with Mathematica needed 319.12 seconds -- but that isn't a proof. Incidently -- any number that fails strong primality testing is definitely not prime. All of the numbers in the megagap have been tested, and we can be certain they are all composite.
A list of currently unverifiable probable primes is maintained at primenumbers.net.
So, arbitrarily large gaps appear between prime numbers. On the complex plane, does the same apply to Gaussian primes?
Figure 2. The Gaussian Primes
Yes, there are arbitrarily large prime-free regions on the complex plane. Define a+bI# as the product of all Gaussian primes n+mI satisfying 0≤a≤n and 0≤b≤m. Define a+bI! as the product of all Gaussian integers n+mI satisfying 0≤a≤n and 0≤b≤m. A prime-free block of Gaussian integers can be found. Just like with regular primes, prime-free blocks with smaller number ranges can be found.
I close with three problems.
Puzzle 1: Divide the numbers {2 3 5 7 11 13 17} into two sets that have products n and n+1.
Puzzle 2: Factor two consectutive numbers higher than {5909760,5909761} into numbers all smaller than 20.
Puzzle 3: What is the smallest 6×6 prime-free Gaussian integer block?
References:
Cramer, Harold "On the order of magnitude of the difference between consecutive prime numbers," Acta. Arithmetic, 2, 23-46. 1936.
Lifchitz, Henri. Probable Prime Top 5000. http://www.primenumbers.net/prptop/prptop.php.
Martin, Marcell. Primo Primality Proving. http://www.ellipsa.net/.
Nicely, Thomas R. First Occurrence Prime Gaps. http://www.trnicely.net/gaps/gaplist.html.
Peterson, Ivars. MathLand: Prime Gaps. http://www.maa.org/mathland/mathland_6_2.html
Wagon, Stan. Mathematica in Action, 2nd edition. Springer-Verlag, 1999.
Weisstein, Eric W. "EllipticCurvePrimalityProving.", "PrimeNumberTheorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html
http://mathworld.wolfram.com/PrimeNumberTheorem.html,Mathematica Code for Figure 1:
primegaps = {{1,2}, {2,3}, {4,7}, {6,23}, {8,89}, {14,113}, {18,523}, {20,887}, {22,1129}, {34,1327}, {36,9551}, {44,15683}, {52,19609}, {72,31397}, {86,155921}, {96,360653}, {112,370261}, {114,492113}, {118,1349533}, {132,1357201}, {148,2010733}, {154,4652353}, {180,17051707}, {210,20831323}, {220,47326693}, {222,122164747}, {234,189695659}, {248,191912783}, {250,387096133}, {282,436273009}, {288,1294268491}, {292,1453168141}, {320,2300942549}, {336,3842610773}, {354,4302407359}, {382,10726904659}, {384,20678048297}, {394,22367084959}, {456,25056082087}, {464,42652618343}, {466,127976334671}, {474,182226896239}, {486,241160624143}, {490,297501075799}, {500,303371455241}, {514,304599508537}, {516,416608695821}, {532,461690510011}, {534,614487453523}, {540,738832927927}, {582,1346294310749}, {588,1408695493609}, {602,1968188556461}, {652,2614941710599}, {674,7177162611713}, {716,13829048559701}, {766,19581334192423}, {778,42842283925351}, {804,90874329411493}, {806,171231342420521}, {906,218209405436543}, {916,1189459969825483}, {924,1686994940955803}, {1132,1693182318746371}, {1184,43841547845541059}, {1198,55350776431903243}, {1220,80873624627234849}}
ListPlot[Map[First[#]/Log[Last[#]]^2 &, pr], PlotJoined -> True, PlotRange -> {0, 1}];
Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.
Ed Pegg Jr. is the webmaster for mathpuzzle.com. He works at Wolfram Research, Inc. as the administrator of the Mathematica Information Center.