Number of digits until a prime is reached

Begin with a random digit from 1 to 9. Add a random digit to the right-hand side from 0 to 9 until a prime number is reached. How many digits are necessary in the avarage ?

More precisely: Let X be the number of digits until a prime is reached. Does E(X) exist, and if so, is there a suitable estimate?

Answer

Fix a real constant c>0, and consider the following game:

At round n, there is a min probability that you win the game. Otherwise, you go on to round n+1.

One may ask, what is the expected number of rounds it will take to win the game? Instead of trying to compute this exactly, let’s us the weaker question: is this expectation finite or not? Note that for any c > 0, the probability of winning in round n will eventually be c/n.

The chance of not winning after n rounds is:

S_n:=\left(1 – \frac{c}{1}\right)\left(1 – \frac{c}{2}\right)
\ldots \left(1 – \frac{c}{n}\right).

If c > 1/2, the first few factors have to be adjusted, of course. To estimate this product for big n,
take the logarithm and use the estimate
\log(1-x) \sim -x which is accurate for small x to get:

\log(S_n) \sim – \sum \frac{c}{n} + O(1) \sim -c \log(n) + O(1),

or that \displaystyle{S_n \sim \frac{A}{n^{c}}} for some constant A > 0. It follows that the chance of winning after exactly n rounds is:

(1 – S_n) – (1 – S_{n-1}) \sim \frac{B}{n^{1+c}},

for another constant B,
and thus the expected number of rounds required may be estimated by:

\sum_{n=1}^{\infty} n(S_{n-1} – S_n) \sim \sum \frac{B}{n^c},

which is infinite if c \le 1, and finite otherwise.
In particular, if c \le 1, the expected length of the game is infinite, and if c > 1, the expected length is finite. Of course, by Kolmogorov’s zero-one law, the expectation that you eventually win is 1.

Let’s compare this to your game. At round n, you have an n-1 digit number to which you randomly append another digit. The chance that an n-digit number is prime will be:

\frac{\pi(10^n) – \pi(10^{n-1})}{10^n – 10^{n-1}} \sim \frac{1}{n \log(10)}

Now of course in your game, the numbers are not exactly random, because they satisfy some prior conditions (namely, that they do not admit any intial string of digits which are not prime). How does this change the analysis? I suspect, that for large n, it does not make much difference, and I also suspect that it will be impossible to prove this. However, it suggests what the answer to your game is: because 1/\log(10) < 1, the expected length of the game is infinite.

Here are two variations:

  1. Start with a random positive integer, then append one of the digits 1, 3, 7, or 9. A "random" n-digit number with this last digit is prime with probability (10/4) \cdot 1/n \log(10). Yet now

\frac{10}{4 \log(10)} = 1.08573\ldots > 1,

so the game (from any starting position should have finite expectation.

  1. Start with a random integer and play the same game in binary. Since 1/\log(2) > 1, one also conjecturally has a finite expectation.

Attribution
Source : Link , Question Author : Peter , Answer Author : suitcase381

Leave a Comment