Gaps between consecutive primes

Introduction

The computation of the first occurrence of prime gaps of a given (even) size between consecutive primes has some theoretical interest [1, problem A8], [2]. Let p_k be the k-th prime number, i.e., p_1=2, p_2=3, p_3=5, ..., and let g_k=p_(k+1)-p_k be the gap between the consecutive primes p_k and p_(k+1). Harald Cramér [3] conjectured, based on probabilistic ideas, that the large values of g_k grow like (log p_k)^2. Our empirical data does not allow us to discriminate between this growth rate and, for example, (log pi(p_k))^2, where pi(x) is the usual prime counting function (note that pi(p_k)=k). Furthermore, the bounds presented below suggest yet another growth rate, namely, that of the square of the so-called Lambert W function. These growth rates differ by very slowly growing factors (like log log p_k). Much more data is needed to verify empirically which one is closer to the true growth rate.

Let P(g) be the least prime such that P(g)+g is the smallest prime larger than P(g). The values of P(g) are bounded, for our empirical data, by the functions

                         0.5                                     0.5
                  0.5   g                                 0.5   g
P_min(g) = 0.12  g     e        and    P_max(g) = 30.83  g     e     .

For large g, there bounds are in accord with a conjecture of Marek Wolf [4].

Computational results

Our prime gap computations are a by-product of our Goldbach conjecture verification effort [5]. We have computed the gaps between all prime numbers smaller than 4·10^18, and, so far, double-checked our results up to 4·10^17 (see the detailed status of this extensive computation). Our results agree with whose presented in [6], [7], [8], and [9]. In this table [14KiB, compressed with gzip] we present the values of P(g) we were able to compute, as well as counts of the number of times each gap occurred. The record-holders, i.e., numbers larger than all previous ones of the same kind, are clearly marked in the table. The following figure presents a graph with the available values of P(g). The black line represents the lower bound for P(g) suggested by Cramér's conjecture.

The two kinds of record-holders marked in the table mentioned above correspond to the values of P(g) closer to one of the two bounds presented in the introduction. In this figure it can be seen that the first occurrence of a prime gap of 1132 is abnormally small.

Let D(x;g) be the relative frequency of occurrence of the gap g for all prime numbers not larger than x. The following figure presents a graph of this function, computed for our current verification limit of the Goldbach conjecture.

The approximate exponential decay of D(x;g) is explained in [10]. It is visible in this figure that the values of D(x;g) when g is a multiple of 6=2·3 (white dots) are larger than those of their neighbors (yellow dots); those of the multiples of 30=2·3·5, and of 210=2·3·5·7, are even larger.

sqrt(2 N(x;g) log log N(x;g))

N(x;6) is larger  than N(x;30) for x <= 1.74274357320*10^35
N(x;6) is smaller than N(x;30) for x >= 1.74274357327*10^35

N(x;30) is larger  than N(x;210) for
  x <= 6.42869106260176003801404998376634178448636748209672
         30934734000364513469429976733667048809926190112851
         62815790254884411833280961248151172061805903500614
         28807728994628470520846144445274265143048582533167
         857*10^425
N(x;30) is smaller than N(x;210) for
  x >= 6.42869106260176003801404998376634178448636748209672
         30934734000364513469429976733667048809926190112851
         62815790254884411833280961248151172061805903500614
         28807728994628470520846144445274265143048582533167
         861*10^25

Top 50

The following table presents the 50 largest g (prime gaps) found so far, with P(g)<4·10^18, either by contributors to this project or by other discoverers (those have an * before the discoverer name). Repeated values of g were excluded from this list.

Contributors

The following table presents some details about the contribution of all (past and present) individuals or organizations which donated computing power to this project.

This work was partially supported by the National Center for Supercomputing Applications and utilized the NCSA Xeon cluster.

This research was partially supported by an allocation of advanced computing resources supported by the National Science Foundation. Part of the computations were performed on Kraken (a Cray XT5) at the National Institute for Computational Sciences.

References

Additional links

• Our Goldbach conjecture verification page.
• Our twin prime gaps page.
• MathWorld's k-tuple conjecture page.
• The top-20 prime gaps page.