Ivars Peterson's MathTrek

June 2, 1997

Prime Gaps

A prime is a whole number (other than 1) that is evenly divisible only by itself and 1. That simple definition leads to following sequence of numbers: 2, 3, 5, 7, 11, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, and so on.

One of the mysteries of primes concerns their distribution. Generally speaking, primes become more scarce as the numbers get larger. In other words, as the numbers of the sequence increase, the intervals between primes get longer on the average, though in a somewhat irregular fashion.

Though many mathematicians have focused on characterizing the distribution of primes (see Prime Theorem of the Century), the related question of the nature of the gaps between successive primes has exerted its own fascination. The size of the gaps between consecutive primes gives an indication of the distribution of primes in short intervals.

It's quite easy to show that there exists a string of at least N consecutive composite integers for any given value of N. In other words, you can have gaps between primes as wide as you wish.

For example, one can readily find a prime gap consisting of 3 composite numbers. Just looking at a table of primes gives 8, 9, and 10 as the first instance of such a gap. It's also possible to use a formula that guarantees the presence of N consecutive composite numbers: (N + 1)! + 2, (N + 1)! + 3, (N + 1)! + 4, É, (N + 1)! + (N + 1). To find a triple, N = 3, and you get the sequence (3 + 1)! + 2, (3 + 1)! + 3, and (3 + 1)! + 4, where (3 + 1)! = 4! = 4 x 3 x 2 x 1 = 24. The numbers are 26, 27, and 28.

So, the formula works, but it typically doesn't give the first prime gap of length N. That might occur well before (N + 1)! + 2. No one, for example, has yet established where the first prime gap of 1,000 is found, though some progress has been made. Sol Weintraub of Queens College (City University of New York) has identified two gaps greater than 1,000 at lower levels than previous reports. In one case, a gap of 1,012 occurs after the prime: 7,067,004,589,474,700,107,580,471,164,301,146,083,123,187,459.

Thomas R. Nicely of Lynchburg College in Virginia, who was responsible for setting off the furor about flawed arithmetic performed by the original Pentium microprocessor (see Pentium Bug Revisited), has a long-term project aimed at exhaustively searching for prime gaps. By last summer, his search had reached 3.6 x 10^14, and the largest gap he had identified was 906, which occurred around 2 x 10^14 digits. A gap of 1,000 seems within reach of Nicely's effort.

Mathematicians have now also obtained research results that suggest strategies for systematically finding consecutive primes separated by a gap of a given length, though not necessarily the first occurrence of such a gap. Pamela A. Cutter, a graduate student at the University of Georgia in Athens, has used this approach to find consecutive primes with gaps corresponding to every even integer from 746 to 1,000.

For a long time, the largest known prime gap consisted of 1,411 consecutive composite numbers. Recently, Harvey Dubner, an electrical engineer in Westwood, N.J., who has a passion for big primes, reported finding several larger prime gaps. The largest one consists of 18,828 consecutive composite numbers, bracketed at the upper end by a prime of 607 digits. Dubner has also found a gap of 12,540 where the primes are 385 digits long, and 15 other gaps greater than 12,540.

There's no shortage of game in these prime hunts.

Copyright © 1997 by Ivars Peterson.

References:

______. 1993. Dubner's primes. Science News 144(Nov. 20):331.

Ribenboim, Paulo. 1989. The Book of Prime Number Records, 2nd ed. New York: Springer-Verlag.

Weintraub, S. 1993. A prime gap of 864. Journal of Recreational Mathematics 25:42-43.

Interesting recent papers on prime number gaps are available at http://www.ift.uni.wroc.pl/~mwolf/.

Comments are welcome. Please send messages to Ivars Peterson at. ipeterson@maa.org