# Expected value of iterations until prime number

I came along a reddit post which described an interesting process described by the following set of rules:

2. Generate a random digit (0-9) and append it to the string
3. If the resulting string is a prime number, terminate the process. If not, repeat steps 2 and 3

The person who proposed this process was interested in the distribution of the amount of digits of the string once the process has terminated (Z). In this post I aim learn more about this process by introducing it to the math.stackexchange community. Additionally, I propose a simple approximation of the expected value of Z by utilizing some (quite heavy) assumptions.

The prime number theorem (PMT) states that $$\frac{N}{ln(N)}$$ is a good approximation of the number of primes less than or equal to $$N$$. Using the PMT, we can approximate the density of primes up to a certain number $$N$$. More specifically, we can approximate the density of primes across a certain magnitude (e.g. from 10 to 99). Lets consider the magnitude 'of one digit'. Normally, this would entail the numbers from 0 up to 9. However, to avoid potential issues of strings with leading zero's, only the numbers 1 through 9 are considered for the first iteration. According to the PMT, amount of primes across this magnitude is $$\frac{9}{ln(9)}-\frac{0}{ln(0)}$$ = $$\frac{9}{ln(9)}$$. Hence, the density of primes across this magnitude (can be found by dividing by the amount of possible digits and) is given by $$\frac{1}{ln(9)}$$. Let's now consider the magnitude 'of two digits' (e.g. from 10 up to 99). A similar derivation shows that the density of primes across this magnitude is $$\frac{99}{90 ln(99)}-\frac{10}{90 ln(10)}$$.

A method of computing the expected value of Z, is computing the probabilities of Z being equal to each number (e.g. $$P(\textbf{Z}=1)$$, $$P(\textbf{Z}=2)$$, ...). Note that, according to the PMT, the probability that a prime appears after one iteration of the process is $$\frac{1}{ln(9)}$$. However, we can not simply use the density of primes across the magnitude 'of two digits' as $$P(\textbf{Z}=2)$$. To be more precise, the calculated density is $$P(\textbf{Z}=2|\textbf{Z}>1)$$. Hence, we need to multiply it by the probability that Z is bigger than 1 to yield $$P(\textbf{Z}=2|\textbf{Z}>1)P(\textbf{Z}>1) = P(\textbf{Z}=2)$$. Note that $$P(\textbf{Z}>1) = 1 - P(\textbf{Z}=1)$$, yielding $$P(\textbf{Z}=2) = (\frac{99}{90ln(99)}-\frac{10}{90ln(10)}) \cdot (1 - \frac{1}{ln(9)})$$. Continuing this process for the magnitude 'of three digits' yields P(Z=3) = $$(\frac{999}{900ln(999)}-\frac{100}{900ln(100)}) \cdot (1 - P(\textbf{Z}=1) - P(\textbf{Z}=2))$$ = $$(\frac{999}{900ln(999)}-\frac{100}{900ln(100)}) \cdot (1 - \frac{1}{ln(9)} - (\frac{99}{90ln(99)}-\frac{10}{90ln(10)}))$$.

In general, we see that that the kth term of the sequence of probabilities can be described by $$$$p_{k} = (\frac{10^k-1}{(9\cdot10^{k-1})ln(10^k-1)} - \frac{10^{k-1}}{(9\cdot10^{k-1})ln(10^{k-1})}) \cdot (1 - \sum^{k-1}_{i=1} p_{i})$$$$ It should be noted that $$\frac{10^{k-1}}{(9\cdot10^{k-1})ln(10^{k-1})}$$ is not defined for $$k=1$$. Thus, we consider it to be zero, yielding (our previously derived) $$p_1 = \frac{1}{ln(9)}$$. For big enough k (which in actuality already works for small k), we have that $$10^k-1 \approx 10^k$$, simplifying the $$p_k$$'s to $$\frac{9k-10}{9k(k-1)ln(10)}$$.

This entire derivation assumes that the density of primes is independent across a previous string being prime not not. For example, we assume that a random digit appended to 20 has the same probability of resulting in a prime as appending it to 31 (even though 31 is prime and 20 is not).

All in all, computing $$E(\textbf{Z}) = \sum^{\infty}_{i=1} i \cdot p_i$$ by simulation reveals that $$E(\textbf{Z}) = \infty$$. Here, we used the simplified formula for $$p_k$$ for $$k > 10$$.

New contributor
Levi Rohring is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• I would suggest simulation. The dependencies between the various stages seem hard to cope with analytically, though heuristic arguments might be available. Speaking loosely, most paths terminate quickly (it seems to me). Paths that don't terminate quickly might go on a very long time.
– lulu
Commented Jul 6 at 11:22
• I am pretty sure someone asked this before. A long time ago , I asked a very similar question with the only difference that I started with some positive integer to avoid leading zeros. Commented Jul 6 at 14:42
• @Peter I have edited my original post with (a.o.) implementing the idea of not considering leading zero's. Commented 2 days ago
• @lulu I have edited my original post with (a.o.) implementing a computation of E[Z] by simulation. Commented 2 days ago
• I guess this is the post Peter is refering to.
– Sil
Commented 2 days ago