Goldbach conjecture verification


Introduction News Results Top 50 Contributors References Links Contact [Up]

Introduction

The Goldbach conjecture is one of the oldest unsolved problems in number theory [1, problem C1]. In its modern form, it states that every even number larger than two can be expressed as a sum of two prime numbers.

Let n be an even number larger than two, and let n=p+q, with p and q prime numbers, p<=q, be a Goldbach partition of n. Let r(n) be the number of Goldbach partitions of n. The number of ways of writing n as a sum of two prime numbers, when the order of the two primes is important, is thus R(n)=2r(n) when n/2 is not a prime and is R(n)=2r(n)-1 when n/2 is a prime. The Goldbach conjecture states that r(n)>0, or, equivalently, that R(n)>0, for every even n larger than two.

In their famous memoir [2, conjecture A], Hardy and Littlewood conjectured that when n tends to infinity, R(n) tends asymptotically to (i.e., the ratio of the two functions tends to one)

                         n                         p-1
N2(n) = 2 C       ----------------     PRODUCT     --- ,
           twin   (log n)(log n-2)   p odd prime   p-2
                                     divisor of n

where

                       p(p-2)
C     =    PRODUCT     -------  = 0.66016181584686957392...
 twin    p odd prime   (p-1)^2

is the twin primes constant. In [3], Crandall and Pomerance suggest replacing the factor

       n
----------------
(log n)(log n-2)

appearing in the formula of N2(n) by the asymptotically equivalent factor

        n-2         dx
INTEGRAL      --------------- .
        2     log(x) log(n-x)

The numerical evidence supporting this conjectured asymptotic formula is very strong. Up to 10^10, the Crandall-Pomerance formula does not deviate from R(n) by more than 40150, and up to 2^40 it does not deviate from R(n) by more than 401900.

Let us order the r(n) Goldbach partitions of n by increasing order of the smallest prime of the partition. More precisely, let us denote the two primes of the i-th Goldbach partition of n by p(n;i) and q(n;i), with p(n;i) <= q(n;i) and p(n;i) < p(n;i+1). In order to verify the Goldbach conjecture for a given n, it is sufficient to find one of its Goldbach partitions. Our strategy will be to find the minimal Goldbach partition n=p(n;1)+q(n;1), i.e., the one that uses the smallest possible prime number p(n)=p(n;1). As in [4], for every prime q we will denote by S(q) the least even number n such that p(n)=q.

News

February 1, 2005: 2·10^17 reached.
March 20, 2005: 10^17 double checked.
December 26, 2005: 3·10^17 reached.
June 5, 2006: 4·10^17 reached.
September 28, 2006: interval between 7·10^17 and 10^18 checked.
February 19, 2007: 5·10^17 reached.
February 23, 2007: interval between 6·10^17 and 7·10^17 checked.
April 25, 2007: 10^18 reached.
February 16, 2008: 11·10^17 reached.
July 14, 2008: 12·10^17 reached.
July 24, 2009: 15·10^17 reached.
December 23, 2009: 16·10^17 reached.
January 5, 2010: interval between 19·10^17 and 20·10^17 checked.
March 24, 2010: interval between 18·10^17 and 19·10^17 checked.
August 24, 2010: interval between 17·10^17 and 18·10^17 checked.

Computational results

We have implemented a program that finds the minimal Goldbach partition of every even integer larger than four. In order to do this efficiently, the computation intensive parts of the program were written in assembly language (for the IA32 instruction set). A very efficient cache friendly implementation of the segmented sieve of Eratosthenes was used to generate the prime numbers (see our speed comparison chart [18k, PDF] between several Intel and AMD CPUs). For each interval of 10^12 integers, we record the number of times each (small) prime is used in a minimal Goldbach partition, as well as the even integer where it was first needed. Because it takes very little extra time, we also record information about the gaps between consecutive primes, viz., how many times each gap occurs, and its first occurrence. On a 2.2GHz Athlon64 3500+ processor, testing an interval of 10^12 integers near 10^18 takes close to 75 minutes. The execution time of the program grows very slowly, like log(N), where N is the last integer of the interval being tested, and it uses an amount of memory that is roughly given by 13 sqrt(N) / log(N). The program is now running on the spare time of some computers, either under GNU/Linux or under Windows XP, and on the Kraken supercomputer. We have reached 1.6·10^18 in December 2009, and are now extending our computations to 2·10^18. Our long-term goal is to reach 4·10^18.

The following table presents an overview of the current status of this massive computation. Each cell represents an interval of 10^15; its background color indicates its computational status (green for double-checked, yellow for single-checked, and red for not yet done or not yet fully checked), and its brightness indicates if counts of the primes in each of the 32 residue classes modulo 120 are available (bright) or not (not so bright) to perform an initial check of the correctness of the computation on each interval of 10^15 (prime counts for each interval of 10^12 are also available to perform correctness checks).

0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019
... (same state) ...
0080 0081 0082 0083 0084 0085 0086 0087 0088 0089 0090 0091 0092 0093 0094 0095 0096 0097 0098 0099
0100 0101 0102 0103 0104 0105 0106 0107 0108 0109 0110 0111 0112 0113 0114 0115 0116 0117 0118 0119
0120 0121 0122 0123 0124 0125 0126 0127 0128 0129 0130 0131 0132 0133 0134 0135 0136 0137 0138 0139
0140 0141 0142 0143 0144 0145 0146 0147 0148 0149 0150 0151 0152 0153 0154 0155 0156 0157 0158 0159
0160 0161 0162 0163 0164 0165 0166 0167 0168 0169 0170 0171 0172 0173 0174 0175 0176 0177 0178 0179
... (same state) ...
0320 0321 0322 0323 0324 0325 0326 0327 0328 0329 0330 0331 0332 0333 0334 0335 0336 0337 0338 0339
0340 0341 0342 0343 0344 0345 0346 0347 0348 0349 0350 0351 0352 0353 0354 0355 0356 0357 0358 0359
0360 0361 0362 0363 0364 0365 0366 0367 0368 0369 0370 0371 0372 0373 0374 0375 0376 0377 0378 0379
... (same state) ...
0960 0961 0962 0963 0964 0965 0966 0967 0968 0969 0970 0971 0972 0973 0974 0975 0976 0977 0978 0979
0980 0981 0982 0983 0984 0985 0986 0987 0988 0989 0990 0991 0992 0993 0994 0995 0996 0997 0998 0999
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019
... (same state) ...
1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399
1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419
1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439
1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459
1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479
... (same state) ...
1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599
1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619
1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639
1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659
1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679
1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699
... (same state) ...
1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759
1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779
1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799
... (same state) ...
2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019
2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039
... (same state) ...
2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299
2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319
... (same state) ...
2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799
2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819
... (same state) ...
2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979
2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999
3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019
3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039
... (same state) ...
3960 3961 3962 3963 3964 3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979
3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995 3996 3997 3998 3999

So far, we have tested all consecutive even numbers up to 161·10^16, and double-checked our results up to 10^17. Some (448) extra intervals of 10^15 were also tested. About 477.9 single-core CPU years were used to do all this. At least 51.45% of the work necessary to reach 4·10^18 is already done.

As far as we are aware, the previous record of computation was 4·10^14 [5]. As expected, no counter-example of the conjecture was found. In this table [23k, compressed with gzip] we present all values of S(p) we were able to compute, as well as counts of the number of times each (small) prime was used in a minimal Goldbach partition. The record-holders, i.e., numbers larger than all previous ones of the same kind, are clearly marked in the table, which extends the tables 1 and 2 of [4] and table 1 of [5]. The following figure presents a graph with the available values of S(p); the cyan dots represent data which is not known for certain to be a first occurrence.

Graph of S(p)

The values of S(p) are bounded, for our empirical data, by the functions

                         0.4                                     0.4
                  0.4   p                                 0.4   p
S_min(p) = 0.06  p     e        and    S_max(p) = 11.05  p     e     .

The two kinds of record-holders marked in the table mentioned above correspond to the values of S(p) closer to one of the two bounds. For large p the values of S(p) appear to be slowly approaching the upper bound; hence, the asymptotic growth rate of S(p) probably has a different functional form. In [6] it was stated, based on probabilistic considerations, that p should not grow faster than log^2 S(p) log log S(p). This appears to be false (for this to be true the data points should be above the black line of the figure, which is clearly not the case). Indeed, it appears that the growth rate of the black curve is too large. Thus, the estimate log^2 S(p) log log S(p) appears to be too small. It was found that for all our data p can be reasonably well approximated by 0.33(log S(p) log log S(p))^2.

Let D(x;p) be the relative frequency of occurrence of the prime p in the minimal Goldbach partition of the even 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;p)

Besides the expected near exponential decay of D(x;p), it is interesting to observe that there exists a distinct difference of behavior in the values of this function when p is a multiple of three plus one (white dots) and when it is not (yellow dots). Cyan dots represent primes of minimal Goldbach partitions 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 p (least primes of a Goldbach partition) found so far, with S(p)<4·10^18, either by contributors to this project or by other discoverers (those have an * before the discoverer name). Repeated values of p were excluded from this list. A question mark indicates a first known occurrence; the true value of S(p) may be smaller than the one given.

  Rank     p     S(p)     Discoverer  
  1     9341     906 03057 95622 79642     John Fettig & Nahil Sobh  
  2     9203     1348 11357 94295 47486     Siegfried "Zig" Herzog  
  3     9161     887 12380 30778 37868     Siegfried "Zig" Herzog  
  4     8951     914 47723 42519 16254     John Fettig & Nahil Sobh  
  5     8941     555 27435 15567 50822     Siegfried "Zig" Herzog  
  6     8933     258 54942 69161 49682     Siegfried "Zig" Herzog  
  7     8821     ? 1670 95614 81435 30128     Tomás Oliveira e Silva  
  8     8737     764 63115 78502 42766     Siegfried "Zig" Herzog  
  9     8719     1570 80604 90039 48202     Tomás Oliveira e Silva  
  10     8699     ? 2994 28857 66127 17268     Tomás Oliveira e Silva  
  11     8689     1302 37600 11943 70768     Siegfried "Zig" Herzog  
  12     8681     771 06523 23704 26528     Siegfried "Zig" Herzog  
  13     8677     ? 1928 32489 01056 96568     Tomás Oliveira e Silva  
  14     8663     1262 36426 84331 28726     Siegfried "Zig" Herzog  
  15     8641     517 71184 25980 37624     Tomás Oliveira e Silva  
  16     8629     1238 28931 11321 16112     Siegfried "Zig" Herzog  
  17     8623     1211 65003 16991 77606     Tomás Oliveira e Silva  
  18     8609     ? 1872 49629 32659 49398     Siegfried "Zig" Herzog  
  19     8573     1134 05983 29344 00206     Siegfried "Zig" Herzog  
  20     8563     280 46026 69116 44252     Tomás Oliveira e Silva  
  21     8539     941 90839 15563 21548     Siegfried "Zig" Herzog  
  22     8527     1295 15748 05397 26954     Siegfried "Zig" Herzog  
  23     8521     1176 80059 43587 37918     Siegfried "Zig" Herzog  
  24     8501     255 32912 66885 55994     Siegfried "Zig" Herzog  
  25     8443     121 00502 23040 07026     Tomás Oliveira e Silva  
  26     8419     ? 1730 12004 22605 42848     Tomás Oliveira e Silva  
  27     8389     935 18588 11050 28832     Siegfried "Zig" Herzog  
  28     8377     ? 1687 29645 86686 51778     Tomás Oliveira e Silva  
  29     8363     ? 1836 18409 81332 94216     Siegfried "Zig" Herzog  
  30     8353     ? 3005 72975 55741 15146     Tomás Oliveira e Silva  
  31     8317     1174 66775 53428 97766     Siegfried "Zig" Herzog  
  32     8311     968 01877 10387 96678     Siegfried "Zig" Herzog  
  33     8291     1213 29977 13341 88358     Tomás Oliveira e Silva  
  34     8287     1513 81436 06765 55824     Tomás Oliveira e Silva  
  35     8269     1399 33262 23761 69692     Siegfried "Zig" Herzog  
  36     8263     ? 1799 42264 68773 85472     Christian Kern  
  37     8237     738 58938 49384 15324     Siegfried "Zig" Herzog  
  38     8233     859 91428 49938 81646     Siegfried "Zig" Herzog  
  39     8221     823 73843 52613 70264     Siegfried "Zig" Herzog  
  40     8219     934 02286 67772 49126     Siegfried "Zig" Herzog  
  41     8209     1018 39367 39183 10542     Siegfried "Zig" Herzog  
  42     8191     988 62533 26133 96552     Siegfried "Zig" Herzog  
  43     8179     160 77419 18161 16822     Siegfried "Zig" Herzog  
  44     8171     ? 1965 11333 06503 11724     Tomás Oliveira e Silva  
  45     8167     363 90621 18840 77288     Tomás Oliveira e Silva  
  46     8161     ? 1993 00012 14973 75964     Christian Kern  
  47     8147     ? 1920 48768 17405 47918     Christian Kern  
  48     8123     1305 64705 49466 80812     Siegfried "Zig" Herzog  
  49     8117     609 50980 05865 20508     Siegfried "Zig" Herzog  
  50     8111     ? 2018 11677 78771 09814     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     1092399     73 (2)     47 (1)  
  Tomás Oliveira e Silva     All     1033445     300 (11)     56 (5)  
  DETUA     689738     174 (4)     41 (3)  
  Kraken     109000     4 (0)     1 (0)  
  Home     209564     3 (7)     8 (2)  
  IEETA     25143     119 (0)     6 (0)  
  Christian Kern     Germany     48999     0 (3)     0 (2)  
  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     2265717     410 (16)     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] G. H. Hardy and J. E. Littlewood, Some problems of `partitio numerorum'; III: on the expression of a number as a sum of primes, Acta Mathematica, vol. 44, pp. 1-70, 1922.
[3] Richard Crandall and Carl Pomerance, Prime numbers: a computational perspective, Springer-Verlag, 2001.
[4] Matti K. Sinisalo, Checking the Goldbach conjecture up to 4·10^11, Mathematics of Computation, vol. 61, no. 204, pp. 931-934, October 1993.
[5] Jörg Richstein, Verifying the Goldbach conjecture up to 4·10^14, Mathematics of Computation, vol. 70, no. 236, pp. 1745-1749, July 2000.
[6] A. Granville, J. van de Lune, and H. J. J. te Riele, Checking the Goldbach conjecture on a vector computer, in Number Theory and Applications, R. A. Mollin (ed.), pp. 423-433, Kluwer Academic Press, 1989.

Additional links