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?

Solution 1:

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

At round $n$, there is a $\min(1/2,c/n)$ 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.

Solution 2:

Let's assume some hard conjectures, which state that the primes behave like a random set of integers with density $\frac{1}{\log x}$, after removing "local conspiracies" (i.e., all sufficiently large primes are coprime to any fixed integer).

Let $a_n$ be the choice after the first $n$ digits. Then $10^{n}<a_{n+1}<10^{n+1}$. We estimate that a given integer (coprime to $10$) of this magnitude is prime with probability $\frac{1}{n\log 10}$. Thus an arbitrary integer is prime with probability $$p_n=\frac{\phi(10)}{10n\log 10}=\frac{2}{5n\log 10}=\frac{\alpha}{n}$$

So now the question is: I flip a coin with probability $p_n$ of turning up heads at turn $n$. What is the expected number of flips before I get a heads?

This in turn is given by $$E=\alpha\sum_{n=1}^{\infty}\left[\prod_{i=1}^{n-1}\left(1-\frac{\alpha}{i}\right)\right]\sim \alpha\sum_{n=1}^{\infty}\left[\prod_{i=1}^{n-1}\exp\left(-\frac{\alpha}{i}\right)\right]\sim\alpha\sum_{n=1}^{\infty}e^{ -\alpha\log n}=\alpha\zeta(\alpha)$$ where $\zeta$ is the Reimann zeta function. But since $\alpha < 1$, this seems to suggest that the expection diverges; there is no finite point at which you would expect to have found a prime.