Ivars Peterson's MathTrek

October 13, 2003

Goldbach Computations

In 1742, historian and mathematician Christian Goldbach (1690–1764) wrote a letter to Leonhard Euler (1707–1783) in which he suggested, in effect, that every integer greater than 5 is the sum of three prime numbers. A prime number is evenly divisible only by itself and 1.

Nowadays, Goldbach's conjecture is expressed in the following equivalent form: Every even number larger than 2 is the sum of two prime numbers.

Despite centuries of effort, no one has yet been able to prove Goldbach's conjecture. Progress has been slow.

In recent years, mathematicians and other researchers have turned to computers to test the conjecture against larger and larger even numbers. In 2000, Jörg Richstein of the University of Giessen verified the conjecture up to 4 x 1014.

Now, Tomás Oliveira e Silva of the University of Aveiro in Portugal and his coworkers have verified the Goldbach conjecture up to 6 x 1016. "As expected, no counterexample of the conjecture was found," the researchers report.

A pair of primes, p and q, that sum to an even integer, n = p + q, is known as a Goldbach partition of n. For example, the prime pair 11 and 13 is a Goldbach partition of 24. So is the pair 5 and 19.

The strategy is to look for the number of different ways of writing n as a sum of two prime numbers (a Goldbach partition), taking into consideration the order of the two primes. The Goldbach conjecture is then equivalent to the statement that the number of Goldbach partitions is greater than 0. The computational trick is to find the minimal Goldbach partition—the one that uses the smallest possible prime number—for every even integer larger than 4.

In the course of their computations, the researchers also recorded information about the gaps between consecutive primes. These data can then be used to find the first occurrence of prime gaps of a given size between consecutive primes.

A few quirks emerge from analysis of the data accumulated so far. In plotting the relative frequency of occurrence of a prime, p, in the minimal Goldbach partition of the even numbers, you can observe that there is a distinct difference in behavior when p is of the form 3k + 1 and when it is not.

A similar difference shows up in the prime gaps data. When plotting the relative frequency of occurrence of a gap n, you see distinctly different behavior when n is a multiple of 6 (2 x 3), 30 (2 x 3 x 5), or 210 (2 x 3 x 5 x 7).

It's always possible that computations may yet provide some hint on how to prove Goldbach's venerable conjecture.

References:

Tomás Oliveira e Silva and his coworkers describe verification of the Goldbach conjecture to 6 x 1016 at http://www.ieeta.pt/~tos/goldbach.html.

Peterson, I. 2000. Goldbach's Prime Pairs. MAA Online (Aug. 21).

______. 1997. Prime Gaps. MAA Online (June 2).

Richstein, J. 2001. Verifying the Goldbach conjecture up to 4 x 1014. Mathematics of Computation 70:1745-1749. See http://www.informatik.uni-giessen.de/staff/richstein/ca/Goldbach.html.

Information about the Goldbach conjecture is available at http://mathworld.wolfram.com/GoldbachConjecture.html, http://primes.utm.edu/glossary/page.php?sort=GoldbachConjecture, and http://home.flash.net/~mherk/goldbach.htm.

You can see Goldbach's letter to Euler at http://www.informatik.uni-giessen.de/staff/richstein/pic/g-letter.jpg.