Gaps between consecutive primes


Introduction Results Top 50 Contributors References Links Contact [Up]

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. So far, we have computed the gaps between all prime numbers smaller than 1609·10^15, and double-checked our results for all prime numbers smaller than 10^17 (see the detailed status of this extensive computation.) Our results agree with whose presented in [5], [6], [7], and [8]. In this table [13k, 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 cyan dots represent data which is not known for certain to be a first occurrence. The black line represents the lower bound for P(g) suggested by Cramér's conjecture.

Graph of P(g)

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.

Graph of D(x;n)

The approximate exponential decay of D(x;g) is explained in [9]. 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. Cyan dots represent prime gaps known to occur before 4·10^18, but which are outside of the interval used to make this graph.

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. A question mark indicates a first known occurrence; the true value of P(g) may be smaller than the one given.

  Rank     g     P(g)     Discoverer  
  1     1476     1425 17282 44376 99411     Tomás Oliveira e Silva  
  2     1442     804 21283 06866 77669     Siegfried "Zig" Herzog  
  3     1392     1480 03203 79396 34731     Tomás Oliveira e Silva  
  4     1380     1031 50183 31302 43273     Siegfried "Zig" Herzog  
  5     1370     418 03264 59367 12127     * Donald Knuth  
  6     1364     1051 14088 80512 30423     Siegfried "Zig" Herzog  
  7     1360     1153 27764 73035 40597     Siegfried "Zig" Herzog  
  8     1358     523 25522 06146 45319     Siegfried "Zig" Herzog  
  9     1356     401 42992 59991 53707     * Donald Knuth  
  10     1350     1180 35175 22041 37089     Tomás Oliveira e Silva  
  11     1344     753 91763 53808 95597     Siegfried "Zig" Herzog  
  12     1342     1578 16910 61411 87727     Tomás Oliveira e Silva  
  13     1340     ? 1954 31746 71273 10787     Tomás Oliveira e Silva  
  14     1332     ? 3995 49998 38313 31581     Tomás Oliveira e Silva  
  15     1328     352 52122 34513 64323     Tomás Oliveira e Silva  
  16     1322     1106 02843 61874 67937     Siegfried "Zig" Herzog  
  17     1320     605 04633 00290 26447     Siegfried "Zig" Herzog  
  18     1314     1214 11964 65476 13277     Tomás Oliveira e Silva  
  19     1312     1396 48771 92534 03577     Siegfried "Zig" Herzog  
  20     1310     ? 1918 58679 96576 17591     Tomás Oliveira e Silva  
  21     1308     749 56545 75543 71299     Siegfried "Zig" Herzog  
  22     1304     1188 13437 93823 95323     Tomás Oliveira e Silva  
  23     1302     ? 1974 64972 85456 69081     Christian Kern  
  24     1300     1141 04186 63848 33123     Siegfried "Zig" Herzog  
  25     1298     ? 2001 37052 98330 60823     Tomás Oliveira e Silva  
  26     1296     ? 1799 23519 83799 03447     Christian Kern  
  27     1294     ? 1868 32618 47640 55803     Siegfried "Zig" Herzog  
  28     1292     494 65339 43054 48051     Tomás Oliveira e Silva  
  29     1290     ? 2980 70756 30312 38363     António Teixeira  
  30     1288     1134 47753 97384 74479     Siegfried "Zig" Herzog  
  31     1286     1450 32967 22533 64801     João Manuel Rodrigues  
  32     1284     697 54368 16338 14903     Siegfried "Zig" Herzog  
  33     1282     1421 60469 97978 63297     Tomás Oliveira e Silva  
  34     1280     1024 52837 60454 32807     Siegfried "Zig" Herzog  
  35     1278     1011 28688 72760 72703     Siegfried "Zig" Herzog  
  36     1276     445 24991 50530 00907     Tomás Oliveira e Silva  
  37     1274     1430 95361 60482 77509     Tomás Oliveira e Silva  
  38     1272     305 40582 65210 87869     Tomás Oliveira e Silva  
  39     1270     882 94371 39114 24097     Siegfried "Zig" Herzog  
  40     1268     977 14771 57048 17539     Siegfried "Zig" Herzog  
  41     1266     727 08202 05274 68413     Siegfried "Zig" Herzog  
  42     1264     ? 1798 55672 01943 08703     Christian Kern  
  43     1262     1087 11290 02195 54391     Siegfried "Zig" Herzog  
  44     1260     542 41177 19443 51871     Siegfried "Zig" Herzog  
  45     1258     335 80692 75766 51033     Tomás Oliveira e Silva  
  46     1256     571 72613 41060 27067     Tomás Oliveira e Silva  
  47     1254     416 96129 81040 09067     * Donald Knuth  
  48     1252     1032 03208 86468 06901     Siegfried "Zig" Herzog  
  49     1250     733 21493 18131 55339     Siegfried "Zig" Herzog  
  50     1248     218 03472 11942 14273     Tomás Oliveira e Silva  

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.

  Name     Location     Number of  
  tasks  
  Number of first (known) occurrences  
  Minimal Goldbach partitions     Prime gaps  
  Siegfried "Zig" Herzog     PSU     1047399     73 (3)     47 (1)  
  Tomás Oliveira e Silva     All     928876     300 (6)     56 (4)  
  DETUA     633051     174 (1)     41 (3)  
  Kraken     109000     4 (0)     1 (0)  
  Home     161682     3 (5)     8 (1)  
  IEETA     25143     119 (0)     6 (0)  
  Christian Kern     Germany     37000     0 (4)     0 (3)  
  John Fettig & Nahil Sobh     NCSA     33641     2 (0)     1 (0)  
  João Manuel Rodrigues     DETUA     16072     9 (0)     2 (0)  
  António Teixeira     IEETA     14995     0 (0)     0 (1)  
  Carlos Bastos     DETUA     8646     11 (0)     1 (0)  
  SIAS Group     IEETA     7529     2 (0)     0 (0)  
  Rui Arnaldo Costa     IEETA     3847     4 (0)     0 (0)  
  Armando Pinho     IEETA     3285     2 (0)     1 (0)  
  Miguel Oliveira e Silva     DETUA     2659     7 (0)     0 (0)  
  Laurent Desnoguès     France     200     0 (0)     0 (0)  
  All     All     2104149     410 (13)     108 (9)  

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 (http://www.nics.tennessee.edu/).

References

[1] Richard K. Guy, Unsolved problems in number theory, third edition, Springer-Verlag, 2004.
[2] Hans Riesel, Prime numbers and computer methods for factorization, second edition, Birkhäuser, 1994.
[3] Harald Cramér, On the order of magnitude of the difference between consecutive prime numbers, Acta Arithmetica, vol. 2, pp. 23-46, 1936.
[4] Marek Wolf, First occurrence of a given gap between consecutive primes, preprint, April 1997.
[5] Jeff Young and Aaron Potler, First occurrence prime gaps, Mathematics of Computation, vol. 52, no. 185, pp. 221-224, January 1989.
[6] Thomas R. Nicely, New maximal prime gaps and first occurrences, Mathematics of Computation, vol. 68, no. 227, pp. 1311-1315, July 1999.
[7] Thomas R. Nicely and Bertil Nyman, First occurrence of a prime gap of 1000 or greater (unpublished).
[8] Bertil Nyman and Thomas R. Nicely, New prime gaps between 1015 and 5·1016, Journal of Integer Sequences, vol. 6, no. 3, article 03.3.1, August 2003 (published electronically).
[9] Andrew Odlyzko, Michael Rubinstein, and Marek Wolf, Jumping champions, Experimental Mathematics, vol. 8, no. 2, pp. 107-118, 1999. (For a layman explanation of the results of this paper, see Ian Stewart, Jumping champions, Scientific American, vol. 283, no. 6, pp. 80-81, December 2000.)

Additional links