Now for the solution to the question in my previous post, which asked what you can learn about , given the sequence of integers .

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 , we can say with confidence that . If we wait long enough, we can learn as many decimal digits of as we want; in particular, to learn the first *n* decimal digits of , we can just wait for the th 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

Do you see why? Taking the floor of something never makes it bigger, so (in fact, it can never be equal since 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 . Dividing through by *n*, we find that

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

Let’s see how this works. The first few numbers in the sequence are . After seeing the 3, we know that . After seeing the 6, we know that — so we have a better upper bound now (3.5) than we did before (4). After seeing the 9, we know , and so on. Notice that our lower bound hasn't changed yet. That won't happen until we get to , when we learn that . 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 | so far |
---|---|---|

10 | 3.1 | |

100 | 3.14 | |

1000 | 3.1415 | |

10000 | 3.141592 | |

100000 | 3.141592653 | |

1000000 | 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!

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?

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

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.

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

Hi JAM,

Well, you can’t, really. I was describing more of a hypothetical situation where

youdon’t know the value of pi, but someoneelsedoes, and they’re the one generating the sequence.