Extending prime numbers digit by digit while retaining primality

Question

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$?

Also asked on MO, with exactly the same title and content.

Answer 1

Heuristically, almost certainly not.

Let's ask how many survivors of order $\infty$ there are with $d$ digits. Each $d$-digit prime has $9$ possible extensions to a $d+1$ digit number, of which three are divisible by $3$. The probability that $n$ is prime is about $\frac{1}{\ln n}$. Therefore the expected number of prime extensions of a $d$-digit number is $\frac{O(1)}{d+1}$. For each prime extension, the expected number of prime extensions to a $d+2$ digit number is $\frac{O(1)}{d+2}$. The expected total number of $d+m$ digit numbers which are prime and have $m$ prime truncations is therefore less than $\frac{10^d}{d \ln 10} \prod_{i=1}^m \frac{O(1)}{d+i}$, and as $m \to \infty$ this clearly tends to zero at a superexponential rate.

---

To get a bit more quantitative, if we simply take into account our knowledge that the 9 candidate extensions are not divisible by 2 or 5 then we naïvely estimate the constant hidden by $O(1)$ as $9 \left( 2 \cdot \frac54 \cdot \frac{1}{\ln 10}\right) \approx 9.77$. If we explicitly count the extensions for small primes we get $$\begin{matrix} n & O(1) \\ 1 & 18 \\ 2 & 10.14 \\ 3 & 10.27 \\ 4 & 9.83 \\ 5 & 9.83 \\ 6 & 9.75 \\ 7 & 9.69 \\ 8 & 9.65 \end{matrix}$$ For pessimistic estimates we could use $9$ and for optimistic estimates we could use $10$.

Answer 2

In short, highly improbable.

I find it interesting that computed data for "small enough" primes suggests $m_{\text{max}}\approx23\ll \infty$.

This problem looks like a generalization of left-truncatable primes, which are all known and finite.

The only difference is, that you are additionally allowing the starting point (end point) of the truncating sequence to not only include one digit primes, but any prime; (Here, we are not truncating until the last digit, but until the last prime instead).

Because of this, your question cannot be solved by an exhaustive search like left-truncatable primes, and a proof for a largest order survivor will be hard (rigorously proving it exists).

Take for example that whether there are infinitely many of deletable primes is still an open question - they have a similar rule of appending digits, and are also unable to be cracked via exhaustive search.

That's why I'll try to provide some computational data.

I would offer some data for a conjecture that the largest such $m$ is $\approx 23$ and could be in fact, the largest left-truncatable prime.

That is, the left-truncatable longest prime is $357686312646216567629137$, $a_1=7$, $m=23$.

After analyzing first $5\cdot10^5$ primes in PARI/GP, we have:

$$\begin{matrix} I & [10^0,10^1] & [10^1,10^2] & [10^2,10^3] & [10^3,10^4] & [10^4,10^5] & [10^5,5\cdot10^5] \\ m_{\text{avg}} & 14.5 & 13.4396 & 9.1032 & 6.1950 & 4.2134 & 3.3898 \\ m_{\text{max}} & 23 & 22 & 21 & 21 & 20 & 20\\ A_{\text{max}} & 7 & 37 & 739 & 89071 & 154079 & 3759461\\ n_{\text{max}} & 4. & 12. & 131. & 8628. & 14196. & 267350. \end{matrix}$$

Where $m_{\text{avg}}$ is the average order $m$ among primes $A_n,n\in I$, where $m_{\text{max}}$ is the largest order among primes $A_n,n\in I$, and $A_{\text{max}}=a_1,\dots,a_k$ is the survivor of the largest order.

Record holders in intervals $I$:

$B_{\text{max}}=\color{red}{b_{m_{\text{max}}},\dots,b_1}$ the digits appended to it $A_{\text{max}}=\color{blue}{a_1,\dots,a_k}$:

$$\begin{array}{lc} \color{red}{35768631264621656762913}\color{blue}{7}&m=23\\ \color{red}{3576863126462165676291}\color{blue}{37}&m=22\\ \color{red}{267248393498162799393}\color{blue}{739}&m=21\\ \color{red}{383469833999336159769}\color{blue}{89071}&m=21\\ \color{red}{73573324843923499983}\color{blue}{154079}&m=20\\ \color{red}{62361989426669156678}\color{blue}{3759461}&m=20 \end{array}$$

By going for larger and larger primes, we are expecting less prime extensions and on average shorter prime extensions (As Peter's answer suggests), which is now also tangible based on this computed data.

Of course it is still possible that there are large primes that'll have $m\gt23$;

But regarding $m\to\infty$, I would bet against it.

Update: Don't let $m_{\text{max}}$ on $I=[10^i,10^{i+1}]$ being $=23,22,21,21,20,20,\dots$ deceive you.

The first examples that break the pattern of decreasing $m_{\text{max}}$ values (given in the above table):

$$\begin{array}{clc} 538834. & \color{red}{963154572334953666616}\color{blue}{7984759} & m = 21 \\ 593591. & \color{red}{3263756913965427392633}\color{blue}{8857817} & m = 22 \end{array}$$

Going beyond $5\cdot10^5$th prime, I can't find $m\gt23$, the best I'm finding is $m=22$ (so far).

Maybe someone with a stronger search can try to find a new record and beat $A_4=7, m=23$ ?

Answer 3

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

Edit: my main point doesn't work, so I will point out the error below - please see the comments. I'll still leave the answer here since the rest of the math seems ok and maybe the idea is helpful somehow. Interesting question! Very nice to think about.

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

[This part doesn't really make sense] 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$.