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

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.

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.

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.

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

References

Additional links

• Our prime gaps page.
• MathSoft's Hardy-Littlewood Constants page.

Tomás Oliveira e Silva Departamento de Electrónica, Telecomunicações e Informática Universidade de Aveiro 3810-193 AVEIRO PORTUGAL				August 30, 2010
Phone: +351-234-370379 Fax: +351-234-370545		Phone (internal): 23013 Office: DET 237
E-mail address: tos@ua.pt Home page: http://www.ieeta.pt/~tos/