Like the elements in chemistry, prime numbers serve as building blocks in the mathematics of whole numbers. Evenly divisible only by themselves and one, primes are a rich source of speculative ideas that mathematicians often find simple to state but difficult to prove.

The Goldbach conjecture is a prime example of such a conundrum.

In a letter written in 1742 to Leonhard Euler (1707–1783), the historian and mathematician Christian Goldbach (1690–1764) expressed the belief that every integer greater than 5 is the sum of three primes. (See the letter at http://www.mathstat.dal.ca/~joerg/pic/g-letter.jpg and http://www.math.dartmouth.edu/~euler/correspondence/letters/OO0765.pdf.)

Euler replied, pointing out that Goldbach’s statement is equivalent to the conjecture that every even integer greater than or equal to 4 is the sum of two primes. He went on to note, “that every even number is a sum of two primes, I consider an entirely certain theorem in spite of that I am not able to demonstrate it.”

Progress in proving the Goldbach conjecture has been slow. In the best effort to date, Chen Jing-Run proved in 1966 that beyond some large number, every even integer may be written as the sum of a prime number and a number that is either a prime or a product of two primes.

In recent decades, mathematicians and other researchers have turned to computers to test the conjecture against larger and larger even numbers. In 1998, Herman te Riele of the National Research Institute for Mathematics and Computer Science in Amsterdam and his coworkers used a Cray supercomputer as well as improved computational techniques to check that all even numbers up to 10^{14} satisfy the Goldbach conjecture. They also checked the conjecture for a sample of larger even numbers, up to 10^{300}.

“Such computations prove the truth of the Goldbach conjecture for a *finite* set of even numbers, which becomes larger and larger in the course of time, thanks to increasing computer capacity and improved algorithms,” te Riele says. “Such computations may also deepen insight into the problem and *could* possibly give a hint toward the proof or disproof of the Goldbach conjecture for the *infinite* set of all the even numbers.”

“There are strong grounds for believing that Goldbach’s conjecture is true, and It feels like just a matter of time before someone figures out how to prove it,” says Joe Buhler of the Mathematical Sciences Research Institute in Berkeley, Calif. “The real justification is algorithmic. In figuring out how to carry out the carry the computations that far, one has to extend and polish algorithmic programming techniques, and the nature of the scientific advance in this case is much more in algorithmics than in number theory.”

Jörg Richstein of the Institute of Informatics at the University of Giessen, Germany, has now pushed the limit to 4 x 10^{14}. He used a variant of an older method, making it possible to perform the computation with a network of relatively modest computers. Richstein reported his results in a paper to be published later this year in *Mathematics of Computation*.

Richstein’s approach also enabled him to investigate the number of different ways in which an even number can be expressed as the sum of two primes. In general, as the even integers get larger, the number of such prime-pairs increases. For example, there are two such pairs that add up to 20, five pairs that sum to 48, and 998 distinct pairs that sum to 9,998.

This observations suggests that the likelihood of finding the exceptional even number that is not the sum of any two primes dimishes as one searches among ever larger even numbers.

In recent work, Richstein found the number of such sums (or Goldbach partitions) for all even integers up to 500 million. Yannick Saouter of the Institut de Recherche en Informatique de Toulouse in France did the same thing up to 128 million, using a different technique. Note that Goldbach partitions take into account the order of the primes that are summed. For example, 10 has two Goldbach partitions: 3 + 7 and 7 + 3.

Integer |
No. of Goldbach partitions |

10 | 2 |

100 | 6 |

1,000 | 28 |

10,000 | 127 |

100,000 | 810 |

1,000,000 | 5,402 |

10,000,000 | 38,807 |

100,000,000 | 291,400 |

The trend apparent in the data is consistent with various conjectures involving partitions of even numbers and, more generally, the distribution of primes. The data also show wide fluctuations in the number of partitions in going from one even integer to the next. For example, the number of partitions of 30,030 is 905, whereas the neighboring even integer 30,028 has 237 partitions and 30,032 has 225 partitions.

Mathematical proofs of conjectures, however, require more than overwhelming numerical evidence. A prize of $1 million recently offered by a British publisher, promoting a novel in which a mathematician seeks to prove the Goldbach conjecture, could well stimulate new efforts to crack this famous problem.

Unfortunately, the publisher’s rules limit participation to residents of the United Kingdom and the United States who are 18 years or older. The deadline for entries is March 2002.