# Extending prime numbers digit by digit while retaining primality [closed]

I looked at a table of primes and observed the following:

If we choose $$7$$ can we concatenate one digit to the left so as to form a new prime number? Yes, concatenate $$1$$ to obtain $$17$$. Can we do the same with $$17$$? Yes, concatenate $$6$$ to obtain $$617$$. And with $$617$$? Yes, concatenate $$2$$ to obtain $$2617$$. Then we can form $$62617$$. And I could not continue since table gives primes with the last entry $$104729$$.

Now some terminology. Call a prime number $$a_1...a_k$$ a survivor of order $$m$$ if there exist $$m$$ digits $$b_1,...,b_m$$ (all different from zero) so that the numbers $$b_1a_1...a_k$$ and $$b_2b_1a_1..a_k$$ and... and $$b_mb_{m-1}...b_1a_1...a_k$$ are all prime numbers.

Call a prime number $$a_1...a_k$$ a survivor of order $$+ \infty$$ if $$a_1...a_k$$ is a survivor of order $$m$$ for every $$m \in \mathbb N$$.

I would like to know:

Does there exist a survivor of order $$+ \infty$$?

(This question, with exactly the same title and content, was asked on MSE about an hour ago, and I think that I should apologize for asking here and there a same question in so a little time-interval, but, as I thought that somebody will come up very fast with an argument with which question would be decided, and that did not happen, I decided to ask it here also, so that this question receives an attention here also. Yes, it has a recreational flavor, but I hope that you like it.)

Edit: I do not know what exactly to do with this question. At this moment, this question is "on hold". And, it is written: "This question appears to be off-topic for this site. While what’s on- and off-topic is not always intuitive, you can learn more about it by reading the help center. The users who voted to close gave this specific reason:

"This question does not appear to be about research level mathematics within the scope defined in the help center." If this question can be reworded to fit the rules in the help center, please edit your question."

I have a question: If this question is not about research-level mathematics, why we do not have an answer that settles this question? I am of the opinion that with present-day level of mathematics we have the tools to set this question, it is just a question of how to put things together in order to obtain an answer. Also, I am of the opinion that any and every question that generates some discussion, and has an attempts of a solution, and is within reach (or even if it is not within reach) is good for this site, because if at least one person likes a question, that means that there is at least one person for which it is good that a question is here on the site, and not closed. Probably an edit should be about mathematical content of the question, but, I think that I do not need to add anything to mathematical content of this question. Now I am going to drink a coffee and leave a destiny of this question to you.

## closed as off-topic by Asaf Karagila, R. van Dobben de Bruyn, Andrés E. Caicedo, Steven Landsburg, Gerald EdgarJun 18 at 0:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question does not appear to be about research level mathematics within the scope defined in the help center." – Andrés E. Caicedo, Steven Landsburg
If this question can be reworded to fit the rules in the help center, please edit the question.

• this Wikipedia page contains much relevant information: en.wikipedia.org/wiki/Truncatable_prime – Carlo Beenakker Jun 17 at 6:24
• Please don’t post in both sites within such a small time interval. – Arturo Magidin Jun 17 at 6:31
• I feel like this has been discussed before and the best one could do was to assume that the next number is prime at random with probability inversely proportional to the number of digits and to investigate the corresponding birth-death process. This gives you something to believe in case you need to exercise "rational faith" but the truth will, probably, remain unknown for quite a while. The best one can hope for with current techniques would be to show that for every $m$, there is a survivor of order $m$. – fedja Jun 17 at 13:19
• I'm voting to close this question as off-topic because it was asked on Math.SE as well. – Asaf Karagila Jun 17 at 17:47
• On https://www.primepuzzles.net/puzzles/puzz_131.htm near the bottom, there is a 2007 comment by J. K. Andersen (Jens Kruse Andersen) that gives an example of a prime number that can be extended 24 times on the left (ending at the prime 96842946512633189183337876922083307). – Jeppe Stig Nielsen Jun 18 at 7:39

I'd like to offer a heuristic partial answer to a more general question... which relates to some of the discussion in the comments.

I had to generalize the definition to make my argument work, so that $$p$$ is a $$\textit{survivor of order}$$ $$m$$ if there is a set of primes $$\{q_1, \dots, q_m\}$$ such that for every $$k \le m$$, the concatenation of primes $$q_k \ q_{k-1} \ \dots \ q_2 \ q_1 \ p$$ is prime.

A $$\textit{survivor of order}$$ $$\infty$$ is a prime $$p$$ along with an infinite set of primes $$\{q_1, q_2, q_3, \dots \}$$ such that for every $$m$$, the concatenation of primes $$q_m \ q_{m-1} \ \dots \ q_2 \ q_1 \ p$$ is prime.

This is the outline of my argument:

Part 1: Heuristically, it is very likely that for any $$k \in \mathbb{N}$$, and $$n \in \mathbb{N}$$ with $$n > k$$, there is an $$n$$-digit number which is the concatenation of $$k$$ many primes.

Part 2: Using the Heuristic Lemma from Part 1, construct a finitely-branching tree $$T$$ of height $$\omega$$ (an $$\omega$$-tree) whose paths correspond to primes which are concatenations of primes. Then use Kőnig's Lemma to show that $$T$$ must have an infinite path, i.e. a survivor of order $$\infty$$.

PART 1

A MSE question/answer shows that for every $$n \in \mathbb{N}$$, there is a prime number with $$n$$ digits. One of the answers provides more intuition regarding the question:"The number of $$n$$-digit numbers increases much faster than the density of primes decreases so the number of $$n$$-digit primes increases rapidly as $$n$$ increases".

Let $$n \in \mathbb{N}$$. Define $${Q_n}_1$$ to be the number of $$n$$ digit primes, and define $${Q_n}_2$$ to be the number of ways to concatenate primes to make an $$n$$-digit number.

First, I will estimate $${Q_n}_1$$: the number of $$n$$-digit primes.

Let $$n \in \mathbb{N}$$. Let $$k$$ be an $$n$$-digit number. Then $$k < 10^n$$, so a conservative estimate of the likelihood that $$k$$ is prime is $$\frac{1}{\ln(10^n)}.$$

Since there are $$9^n$$ many $$n$$-digit numbers, there are approximately $$\frac{9^n}{\ln(10^n)}$$

many $$n$$-digit numbers which are prime.

Thus, the estimate for $${Q_n}_1$$ is $$\frac{9^n}{\ln(10^n)}$$.

Here is a table which gives the estimated values versus the real values of numbers of primes for a given length.

$$\begin{array}{ | c | c | c | c |} \hline \mbox{ Digits }& \mbox{ Formula } & \mbox{ Estimate of number of primes } & \mbox{ Actual }\\ \hline 1 & \frac{9}{\ln(10)} & 3.91 & 4 \\ \hline 2 & \frac{9^2}{\ln(10^2)} & 17.59 & 21 \\ \hline 3 & \frac{9^3}{\ln(10^3)} & 105.53 & 142 \\ \hline 4 & \frac{9^4}{\ln(10^4)} & 712.35 & 1061 \\ \hline \end{array}$$

Next, I will estimate the number of ways to write an $$n$$-digit number as a concatenation of primes.

Let $$n \in \mathbb{N}$$. I'll assume $$n$$ is odd to make the calculation here slightly simpler. I'm going to estimate the number of ways to write $$n$$ as a concatenation of two primes, and thus the estimate for the number of ways to write $$n$$ as a concatenation of more primes will be greater.

For any $$n \in \mathbb{N}$$ there are $$n-1$$ many ways to see $$n$$ as a concatenation of two numbers. For example the 5-digit number 75319 can be seen as: 7-5319, 75-319, 753-19, or 7531-9 (this is a random example, in the work below each part of the concatenation is a prime number).

Let me show how to estimate the number of ways to write a 5-digit number as a concatenation of primes, then the reader can see how I got the estimate for an $$n$$-digit number.

For a 5-digit number, the first concatenation type is a single digit number followed by a 4-digit number.

There are 4 single digit prime numbers, and there are approximately $$\frac{9^4}{\ln(10^4)}$$ primes which are 4-digits long.

Thus there are approximately $$\frac{4 \cdot 9^4}{\ln(10^4)}$$ many 5-digit numbers which are of the first concatenation type.

There are just as many of the concatenation type which is a 4-digit number followed by a single digit number.

For the concatenation type of a 5-digit number which is a 2-digit number followed by a 3-digit number, there are approximately $$\frac{9^2 \cdot 9^3}{\ln(10^2) \cdot \ln(10^3)}$$ many 5-digit numbers of this concatenation type.

There are the same amount of 5-digit numbers which are of the concatenation type which is a 3-digit number followed by a 2-digit number.

Thus, the total estimate for the number of ways to write a 5-digit number as a concatenation of two primes is

$$2 \ \Bigg( \frac{4 \cdot 9^4}{\ln(10^4)} + \frac{9^2 \cdot 9^3}{\ln(10^2) \cdot \ln(10^3)} \Bigg) = 9411.$$

A worked out argument will give the following estimate for the number of ways to write an $$n$$-digit number as a concatenation of two primes: $$2 \Bigg( \frac{4 \cdot 9^n}{\ln (10^n)} + \frac{9^{n-2} \cdot 9^2}{\ln(10^{n-2})\cdot \ln(10^2) } + \dots + \frac{9^{(n+1)/2} \cdot 9^{(n-1)/2}}{\ln(10^{(n+1)/2}) \cdot \ln(10^{(n-1)/2})} \Bigg) .$$

Thus, the estimate for $${Q_n}_2$$ must be greater than the above number. Thus heuristically, $${Q_n}_2 > {Q_n}_1$$. That is, the number of ways to write an $$n$$-digit number as a concatenation of $$k$$ many primes is greater than the number of $$n$$-digit primes. So, it is likely that for a given $$n$$ and $$k < n$$, there is an $$n$$-digit number which is both prime and a concatenation of primes.

PART 2

If it is true that for every $$n \in \mathbb{N}$$ and $$k < n$$, there is an $$n$$-digit prime which is a concatenation of $$k$$ many primes, then I can imagine constructing an $$\omega$$-tree $$T$$ whose paths correspond to primes which are concatenations of primes. By Kőnig's lemma $$T$$ must have an infinite path, and thus there must be a survivor of order $$\infty$$.

I'd like to expand here to describe $$T$$:

1) $$t \in T$$ if $$t$$ is prime and a concatenation of primes

2) $$s < t$$ in $$T$$ if $$t = s^{\cap}q$$ where $$q \in T$$

Let us order $$T$$ with a lexicographical ordering of the prime "words" created.

First, we can see that $$T$$ is a tree. Then, we can see that the tree is finitely branching via the ordering since there are finitely many primes for each number of digits. Finally, $$T$$ has branches of every height by the Heuristic Lemma of part 1, and thus $$T$$ has height $$\omega$$.

If there is no prime survivor of order $$\omega$$, then $$T$$ is an $$\aleph_0$$-Aronszajn tree, which is impossible. Thus, there must be a prime survivor of order $$\omega$$.