Goldbach conjecture verification

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.
November 6, 2010: 2·10^18 reached.
May 24, 2011: 22·10^17 reached.
July 31, 2011: 25·10^17 reached.
September 13, 2011: 26·10^17 reached.
November 30, 2011: discovery of the minimal Goldbach partition 2795935116574469638=9629+P19.
January 16, 2012: discovery of the minimal Goldbach partition 3325581707333960528=9781+P19.
February 6, 2012: 34·10^17 reached.
February 13, 2012: 35·10^17 reached.
April 4, 2012: 4·10^18, our desired verification limit, reached.
June 18, 2012: 2·10^17 double checked.
September 7, 2012: 3·10^17 double checked.
May 26, 2013: 4·10^17 double checked. No more double checking will be done in the near future.

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 [23KiB, 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 single core of a 3.3GHz core i3 processor, testing an interval of 10^12 integers near 10^18 takes close to 48 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 ran on the spare time of many computers, either under GNU/Linux or under Windows XP. We have reached 2·10^18 in November 2010, and in April 2012 have finally reached 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).

We have tested all consecutive even numbers up to 4·10^18, and, so far, double-checked our results up to 4·10^17 (in all, 581701 intervals of 10^12 were double-checked). About 781.8 single-core CPU years were used to do all this.

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 [24KiB, 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 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). Our data is not enough to resolve this conjecture; the black curve corresponds to the line 1.527 log^2 S(p) log log S(p) (according to the conjecture, all data points should be above the line). 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. In [7] other, probably better, approximations to S(p) are studied in more detail.

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.

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).

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.

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 prime gaps page.
• MathWorld's k-tuple conjecture page.
• Cracking Goldbach's Conjecture (European Grid Infrastructure case studies)