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