Predicting Pi: solution

Now for the solution to the question in my previous post, which asked what you can learn about \pi, given the sequence of integers \lfloor \pi \rfloor, \lfloor 2\pi \rfloor, \lfloor 3\pi \rfloor, \dots.

Nick Johnson commented:

Well, the obvious thing one can learn given just |(10^n)r| is the first n digits of the decimal expansion of r.

For example, when we are given \lfloor 100\pi \rfloor = 314, we can say with confidence that \pi \approx 3.14\dots. If we wait long enough, we can learn as many decimal digits of \pi as we want; in particular, to learn the first n decimal digits of \pi, we can just wait for the 10^nth item of the list.

This seems like an awfully long time to wait, though. Not only that, but if we only look at the first, tenth, hundredth, thousandth,… elements of the sequence, we would be ignoring almost all the information in the sequence! Intuitively, it seems that we should be able to do better by taking more of the sequence into account. And indeed, we can.

The key is to realize that

\lfloor n\pi \rfloor \leq n\pi < \lfloor n\pi \rfloor + 1.

Do you see why? Taking the floor of something never makes it bigger, so \lfloor n\pi \rfloor \leq n\pi (in fact, it can never be equal since \pi is irrational, but that’s not important for our purposes). Also, taking the floor of something reduces it by some amount less than one, so adding one to the floor gives us something bigger than the original; hence n\pi < \lfloor n\pi \rfloor + 1. Dividing through by n, we find that

\displaystyle \frac{\lfloor n\pi \rfloor}{n} \leq \pi < \frac{\lfloor n\pi \rfloor + 1}{n}.

That is, if the nth element of the sequence is k, then we know that \pi must be between k/n and (k + 1)/n. Of course, this works for any number r, not just for \pi.

Let’s see how this works. The first few numbers in the sequence \lfloor \pi \rfloor, \lfloor 2\pi \rfloor, \lfloor 3\pi \rfloor, \dots are 3, 6, 9, \dots. After seeing the 3, we know that 3/1 \leq \pi < 4/1. After seeing the 6, we know that 6/2 \leq \pi < 7/2 — so we have a better upper bound now (3.5) than we did before (4). After seeing the 9, we know 9/3 \leq \pi < 10/3, and so on. Notice that our lower bound hasn't changed yet. That won't happen until we get to \lfloor 8\pi \rfloor = 25, when we learn that 25/8 \leq \pi < 26/8. So our new lower bound is 3.125. But the upper bound at this step, 26/8 = 3.25, is actually worse than the upper bound that we would have found on the previous step, namely 22/7 = 3.142857… So in general, the upper and lower bounds that we find in each step might not be better than all the previous ones; we can just keep the greatest lower bound and the least upper bound that we've seen so far.

So, how good are these bounds? I wrote a little program to compute the best upper and lower bounds for various points in the sequence. Here's a table showing the best lower and upper bounds at various points in the sequence, and the decimal digits they give us confidence about.

Term Best bounds \pi so far
10 \frac{25}{8} < \pi < \frac{22}{7} 3.1
100 \frac{311}{99} < \pi < \frac{22}{7} 3.14
1000 \frac{2818}{897} < \pi < \frac{355}{113} 3.1415
10000 \frac{31218}{9937} < \pi < \frac{355}{113} 3.141592
100000 \frac{208341}{66317} < \pi < \frac{312689}{99532} 3.141592653
1000000 \frac{3126535}{995207} < \pi < \frac{1146408}{364913} 3.1415926535

As you can see, this method does much better than the method of just looking at powers of ten! At n = one million, we already know ten decimal digits of pi; by looking just at the one millionth element of the sequence, we would only know six digits. It turns out that in general, it is the case (which I will not prove) that on average, we can get approximately twice as many decimal digits by finding best upper and lower bounds this way instead of just looking at powers of ten.

In a future post I hope to make a graph of these upper and lower bounds and talk a little bit more about what’s going on—it turns out to be pretty interesting stuff!

About these ads
This entry was posted in convergence, pattern, sequences, solutions and tagged , , , , . Bookmark the permalink.

5 Responses to Predicting Pi: solution

  1. Nick Johnson says:

    Very clever indeed. I knew from your post that there must be a cleverer solution, and indeed, once you demonstrate it it’s quite obvious. It’s a nice math trick in that sense – it’s fairly easy to demonstrate. :)

    This strikes me as vaguely similar to using stochastic processes to learn more about a measurement than you can normally get from the resolution of the measurement device – any relation?

  2. Brent says:

    It does seem similar, although I don’t really know much about what you describe, so I’m not sure.

  3. Rich says:

    Hear me out. Pi is not the only irrational number, but the only one I know of with no discernible pattern. Is there any way to create an equation that accounts for the passing of time, that results in a rational solution? In other words, measure the speed of time by returning the perfect arc to where it started.

  4. JAM says:

    I’m curious. How does one generate the sequence without knowing pi in the first place?

  5. Brent says:

    Hi JAM,

    Well, you can’t, really. I was describing more of a hypothetical situation where you don’t know the value of pi, but someone else does, and they’re the one generating the sequence.

Comments are closed.