Brun’s Constant and the Pentium Bug

Euclid showed by a deliciously simple argument that the number of primes is infinite. In a completely different manner, Euler confirmed the same result. Euler’s conclusion followed from his demonstration that the sum of the reciprocals of the primes diverges:

\displaystyle \sum_{p\in\mathbb{P}} \frac{1}{p} = \infty

Obviously, this could not happen if there were only finitely many primes.

Prime Pairs

Although the prime numbers become sparser among the natural numbers as their size increases, pairs of primes differing by just two continue to appear, albeit with decreasing frequency, as we move to larger and larger numbers. Thus we have prime pairs such as {(3,\,5)}, {(29,\,31)} and {(824\,633\,702\,441,\,824\,633\,702\,443)}.

The question of whether the set of prime pairs is infinite remains unresolved. If we could prove that the sum

\displaystyle \sum_{\{p,p+2\}\subset\mathbb{P}} \left(\frac{1}{p}+\frac{1}{p+2}\right)

diverged, the infinity of the prime pairs would follow. However, this series actually converges. In 1919, Norwegian mathematician Viggo Brun proved that

\displaystyle \sum_{\{p,p+2\}\subset\mathbb{P}} \left(\frac{1}{p}+\frac{1}{p+2}\right) = B_2

where {B_2}, now known as Brun’s Constant, has a value of about 1.9. The value of {B_2} is not known exactly and, indeed, it is not known whether it is rational or irrational (of course, irrationality would imply that the sum is infinite).

The prime number theorem shows that {\pi(n)}, the number of primes less than or equal to {n}, is asymptotic to {n/\log n}:

\displaystyle \pi(n) \sim n/\log n

Let {\pi_2(n)} denote the number of primes {p\le n} for which {p+2} is also prime. Then

\displaystyle \pi_2(n) = O\left( \frac{n(\log\log n)^2 }{(\log n)^2} \right)

Thus, twin primes are fewer than primes by approximately a logarithmic factor. Brun’s Theorem follows from this result. In other words,

\displaystyle \sum_{\{p,p+2\}\subset\mathbb{P}} \left(\frac{1}{p}+\frac{1}{p+2}\right) = \left(\frac{1}{3}+\frac{1}{5}\right) + \left(\frac{1}{5}+\frac{1}{7}\right) + \left(\frac{1}{11}+\frac{1}{13}\right) + \cdots

is either a finite series, or a convergent infinite series with limit denoted by {B_2}. However, the convergence of the series does not tell us whether it is a finite or infinite series, so it does not answer the main question: Are there infinitely many prime pairs?

primepairs-4panels

Sum of reciprocals of primes for increasing upper limits, from 100 (top left) to 1000000 (bottom right).

Direct computations of {B_2} with increasing numbers of twin primes converge very slowly (Fig. 1), and more sophisticated extrapolations are used to estimate the ultimate value. Fig. 2 shows that extrapolation indicates a limiting value marginally larger than 1.9. The intersection of the extrapolating line with the vertical axis is Brun’s constant if the twin prime conjecture is valid. According to this approach, the direct estimation of {B_2(p)} does not exceed 1.9 until the value {p\approx 10^{530}}, far beyond the computational range.

bruns-constant

Extrapolation of computed values of B_2 to a limit of slightly greater than 1.9 [from Sebah and Gourdon (2002)].

The Pentium Bug

In 1995, Thomas Nicely of Lynchburg College, Virginia, showed that {B_2 \approx 1.90216058}. To be on the safe side, Nicely performed all his calculations twice, using two algorithms on two separate computers. He found discrepancies and, after eliminating other possibilities, pinned down the anomalous numerical results to the floating point unit in the brand new Intel Pentium chip, introduced in 1993. The Pentium gave incorrect values for the reciprocals of the twin primes:

\displaystyle \frac{1}{824,633,702,441} \qquad\mbox{and}\qquad \frac{1}{824,633,702,443}

with errors in the tenth decimal place. This is a nice example of how problems in number theory can provide excellent test cases for computer hardware and software.

The cause was discovered to be missing entries in a lookup table used for division in the floating point unit of the chip. Intel recalled the defective processors and estimated that the total cost associated with their replacement would be $ 475 million. Although the errors in the faulty chips were rare, the story generated widespread debate, and caused widespread criticism of how Intel had reacted to the problem.
Sources

{\bullet} Cipra, Barry A. (1995). “How number theory got the best of the Pentium chip”. Science. 267 (5195): 175. doi:10.1126/science.267.5195.175.

{\bullet} Nicely, Thomas (1996): Enumeration to {10^{14}} of the Twin Primes and Brun’s Constant, Virginia J. Sci., Vol. 46, p. 195-204

{\bullet} Sebah, Pascal and Xavier Gourdon, 2002: Introduction to twin primes and Brun’s constant computation.
HTML: http://numbers.computation.free.fr/Constants/constants.html
PDF: http://numbers.computation.free.fr/Constants/Primes/twin.pdf


Last 50 Posts

Categories