Here is a very interesting formula for pi, discovered by
David Bailey, Peter Borwein, and Simon Plouffe in 1995:
Pi = SUM_{k=0 to infinity} 16^{k}
[ 4/(8k+1)  2/(8k+4)  1/(8k+5)  1/(8k+6) ].
The reason this pi formula is so interesting is because
it can be used to calculate the Nth digit of Pi (in base 16)
without having to calculate all of the previous digits!
Moreover, one can even do the calculation
in a time that is essentially linear in N,
with memory requirements only logarithmic in N.
This is far better than previous algorithms for
finding the Nth digit of Pi, which required keeping track of
all the previous digits!
Presentation Suggestions:
You might start off by asking students how they might
calculate the 100th digit of pi using one of the other
pi formulas they have learned. Then show them
this one...
The Math Behind the Fact:
Here's a sketch of how the BBP formula can be used to
find the Nth hexadecimal digit of Pi.
For simplicity, consider just the
first of the sums in the expression, and multiply this by
16^{N}. We are interested in the fractional part
of this expression. The numerator of a given term
in this sum is 16^{Nk}, and it can
be evaluated very easily mod (8k+1) using a binary
algorithm for exponentiation. Division by (8k+1)
is straightforward via floating point arithmetic.
Not many more than N terms of this sum need be evaluated,
since the numerator decreases very quickly as k gets large
so that terms become negligible.
The other sums in the BBP formula are handled similarly.
This yields the hexadecimal expansion of Pi starting at the
(N+1)th digit. More details can be found in the
BaileyBorweinPlouffe reference.
The BBP formula was discovered using the
PSLQ Integer Relation Algorithm. However, the
AdamchikWagon reference
shows how similar relations can be discovered in a way
that the proof accompanies the discovery, and gives
a 3term formula for a base 4 analogue of the BBP result.
How to Cite this Page:
Su, Francis E., et al. "Finding the Nth digit of Pi."
Math Fun Facts.
<http://www.math.hmc.edu/funfacts>.
