### The remarkable BBP Formula

Information that is declared to be forever inaccessible is sometimes revealed within a short period. Until recently, it seemed impossible that we would ever know the value of the quintillionth decimal digit of pi. But a remarkable formula has been found that allows the computation of binary digits starting from an arbitrary  position without the need to compute earlier digits. This is known as the BBP formula.

Early estimates of pi

For millennia, mathematicians have been intrigued by pi. Despite prolonged and intensive study, many simple questions about this number remain unanswered. The digits of pi appear to occur with random frequency, but there is no proof of this. We don’t even know whether any specific digit, say 4, in the decimal expansion occurs infinitely often.

Archimedes approximated pi using polygons drawn within and around a circle. In the plague year of 1666, Isaac Newton evaluated 15 decimal digits of pi, remarking apologetically that he “had no other business at the time.” In 1761 the Swiss mathematician Johann Lambert showed that pi is irrational, so its digits do not repeat in any number base. Over a century later, Lindemann proved that pi is transcendental, implying that no integer polynomial in pi has repeating digits. This also demonstrated the impossibility of solving the ancient Greek problem, to construct a square with the area of a given circle.

The computer era

Since the dawn of the computer era, the number of known digits of pi has grown exponentially. In 1949 over two thousand digits of pi were computed using ENIAC, and John von Neumann sought patterns in the digits but found none. By 1973 pi was known to a million digits, by 1989 a billion and by 2002 a trillion. Currently, more than five trillion digits are known.

It is difficult even for experts to anticipate the advances in computing techniques and in the efficiency of algorithms for computing pi. In his book “The Emperor’s New Mind”, Roger Penrose wrote that we would never know if a string of ten consecutive 7s occurs in pi. But such a string was found within a decade (at about 23 billion digits into the expansion).

The BBP Formula.

In 1997 Bailey, Borwein and Plouffe published a remarkable formula for pi: $\displaystyle \pi = \sum_{k=0}^{\infty}\left[\frac{1}{16^k}\left(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6}\right)\right]$
Because of the factor 16^k, this allows the direct calculation of the hexadecimal digits of pi, beginning at an arbitrary position without any need to compute earlier digits. The discovery of the formula required considerable ingenuity but, once found, its proof is surprisingly simple. For a description of the hunt for the formula and an outline of the proof, see [Bailey et al, 2013].

The BBP formula came as a surprise. It had not been expected that it would be possible to extract digits far into the expansion without crunching out all the earlier digits. Of course, the formula provides only the hexadecimal digits. Subsequent searches for an analogous formula giving the decimal digits have been unsuccessful and it is now doubted if any such formula exists.

Normal Numbers

A number is normal if its digits are distributed “randomly” or, more specifically, if every string of m digits occurs with limiting frequency 10^{-m}. Thus, each digit from 0 to 9 occurs (ultimately) 10% of the time, each pair from 00 to 99 occurs 1%, and so on. A more general definition of normality includes expansions in all number bases.

Proving normality is very difficult except for some specially constructed numbers (e.g. Champernowne’s Number). It is not known if pi is normal but the numerical evidence points towards this. Recent progress gives us hope that an answer may be found within a decade or two.

Sources

David Bailey, Peter Borwein, and Simon Plouffe, 1997: On the rapid computation of various poly-logarithmic constants. Mathematics of Computation, 66, 903–913. NAMS

David H. Bailey, Jonathan M. Borwein, Andrew Mattingly, Glenn Wightwick, 2013: The Computation of Previously Inaccessible Digits of pi^2 and Catalan’s Constant. Not. Amer. Math. Soc., 60, 844-854. MathComp

Wikipedia article: Bailey–Borwein–Plouffe formula [http://en.wikipedia.org/wiki/BBP_formula].