14
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Initial instinct to this says yes since there are an infinite number of primes...fascinating game though! $\endgroup$ – thesmallprint May 3 '17 at 14:29
  • $\begingroup$ It is conjectured that between $n^2$ and $n(n+1)$, there always exists a prime number and also for $n(n-1)$ and $n^2$ (Oppermann's contecture) It seems like the claim "If the number gets large enough, then regardless of the last move, we can always find a move in this game" is slightly weaker than it (but not implied from Oppermann's conjecture). $\endgroup$ – didgogns May 3 '17 at 14:41
  • $\begingroup$ This is essentially yet another variant on Legendre's conjecture that there is always a prime between $n^2$ and $(n+1)^2$. It is very likely to be true (empirically the gaps between primes are found to be far, far smaller) but we don't know any proof. However, we can prove it if you add $2k$ new digits instead of $k$. In fact we can whittle the multiplier of $2$ down to a little more than $1.1$, but to get it down to $1$ would require a substantial breakthrough! $\endgroup$ – Erick Wong May 3 '17 at 14:47
  • $\begingroup$ @ErickWong So should I remove "elementary number theory" tag? $\endgroup$ – Living Hell May 3 '17 at 14:54
  • 1
    $\begingroup$ The tag is probably fine: the question is of elementary nature, but even advanced methods are unable to crack it. $\endgroup$ – Erick Wong May 3 '17 at 17:30
10
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.