Re: Digits of pi

On 2012-01-07, Timothy Murphy <gayleard@xxxxxxxx> wrote:
The Last Danish Pastry wrote:

What is the smallest positive integer, n, such that when n is converted
into its usual string of decimal digits, that string does not occur
anywhere in the first billion digits of the decimal expansion of pi?

I think I know the answer, but I am not totally certain.

I was thinking about this as a problem on probability distributions
(about which I know almost nothing),
and it seemed to me that n would be quite small.

Suppose we consider d-digit numbers.
There are about 10^9 d-digit sequences in the given billion digits.

I'm not at all sure of my reasoning,
but the probability that a _given_ d-digit sequence does not occur
is approximately (1-10^{-d})^{10^9}

If we take d = 9 this is about 1/e.
So it is almost certain that _some_ 9-digit sequence does not occur.

It is certain that some 9-digit sequence does not occur,
as there are only 10^9 - 8 9-digit sequences. However,
this sequence may start with 0, and not give a counterexample.

Your argument just makes it plausible that there is one.

Suppose we take a smaller d.
Let p be the probability that a d-digit sequence does not occur.
Then approximately log p = 10^9 log(1-10^{-d}) = -10^{9-d}.
So p is approximately e^{-10^{9-d}}.

If we take d = 7 this gives p = e^{-100}.
So the probability that some 7-digit sequence does not occur
(this is very crude reasoning) is about 10^7 e^{-100}.
Say 10 = e^3; this gives probability e^{-79},
which is very small, ie all 7-digit sequences almost certainly occur.

If we take d = 8 we get p = e^{-10},
so the probability that some d-digit sequence does not occur
is approximately e^{24-10}, ie it is almost certain.

So my guess is that n = 8.

The probability that the above reasoning is correct is rather small!

This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@xxxxxxxxxxxxxxx Phone: (765)494-6054 FAX: (765)494-0558