Adding digits in this way to primes to obtain another primes

Question

I just created the following "game":

Choose some prime number. If it has $k$ digits then add another $k$ digits to the right to obtain another prime number. Now we have a prime number with $2k$ digits. Now add $2k$ digits to the right of the new number to obtain a new prime number. Repeat the procedure until it is no longer possible to produce new primes in this way.

To clarify, let us take for example $5$. We must add one digit to the right to obtain another prime number, it can be $53$. Now we must add two digits to the right of $53$ to obtain a new prime. It could be $5323$. Now we must add four digits to the right of $5323$ to obtain a new prime. It could be $53231117$ and so on and so on...

Is it true that whatever prime we choose at the beginning that this game never ends? That is, that it is always possible to build larger primes from the smaller ones in this way?

Answer 1

Your operation of adding $k$, $2k$, $4k$, etc digits is the same as $n' \leftarrow 10^k n + c'$ for some $0 \leq c' < 10^k$.

Since we're always doubling digits we can also write $n$ as $10^k + c$. So we want to know if there is a prime between $10^k(10^k+c) + 0$ and $10^k(10^k+c) + 10^k - 1$.

We can ignore the $-1$ at the end as then the upper limit is composite, so it can never be confused for a prime. So is there a prime between $10^k(10^k+c)$ and $10^k(10^k + c + 1)$?

In the worst case this gap is smallest when $c = 0$, so we can simplify to asking whether there is a prime between $10^{2k} $ and $10^k(10^k+1)$. I believe this is an open problem (Opperman's conjecture).

Answer 2

This is closely related to certain unsolved conjectures on the distribution of primes. As such, I suspect proving it would require a major advance in number theory.

You need that for any reachable prime $p$ with $10^n>p>10^{n-1}$, there is a prime between $10^np$ and $(10^n+1)p$. So there certainly needs to be a prime between $M$ and $M+\sqrt M$, where $M=10^np$. Now, except for the fact that there are some restrictions on $M$, this is Oppermann's conjecture. I'd expect the problem to be of similar difficulty, since this still has to hold for lots of values of $M$, and there is no reason why having $M$ of this form should make things any easier.

It is widely believed that Oppermann's conjecture is very true, in the sense that there is a prime between $M$ and $M+f(M)$ for some function $f(M)$ growing much more slowly than $\sqrt M$. A more precise statement of this is Cramér's conjecture. Cramér showed that if the Riemann hypothesis (arguably the most important unsolved problem in mathematics) could be proved, an improved bound on $f(M)$ would follow, but even that bound would be weaker than Oppermann's conjecture!