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
.



Relevant Pages

  • Re: Does a "pure" real valued probability function mak
    ... I further analyze the notion of the sequence representing the rational ... subsequences as there are digits in the repeating terminator, ... Obviously enough the probability to get any particular sequence, ... random counting number, and the sample sequence, an infinite sequence ...
    (sci.logic)
  • Re: Does pI now contain the complete works of Shakespeare?
    ... is normal then that sequence will be found. ... To quantify, the probability of a random sequence of 9,000,000 digits ... enormous number, the googol, is only 10 to the 100. ...
    (talk.origins)
  • Re: user defined function that converts string to float
    ... > I need user defined function that converts string to float in c. ... initial, possibly empty, sequence of white-space characters (as ... point character, then an optional exponent part as defined in ... then a nonempty sequence of hexadecimal digits ...
    (comp.lang.c)
  • Re: Hello There?
    ... to base b if each sequence d_1,...,d_k of base-b digits appears ... a little surprising if the decimal expansion didn't contain the message ... the probability for the message to appear would be ...
    (sci.logic)
  • Re: determinism, freewill, chaos, and circular causality
    ... classes, including sequence prediction, strategic games, function ... the squares each with its decimal digits ... Do the algorithms for generating Pi all require infinite memory? ... numbers" and the qualifcation is that there is no shorter input string ...
    (comp.ai.philosophy)