Extending prime numbers digit by digit while retaining primality
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.
elementary-number-theory prime-numbers recreational-mathematics decimal-expansion
edited Jun 17 at 5:57
Martin Sleziak
asked Jun 17 at 4:21
GrešnikGrešnik
$\begingroup$ One small thing is that in your third paragraph, the end suffices for the $a$ should be $k$, not $m$. $\endgroup$ – John Omielan Jun 17 at 4:30
$\begingroup$ I would be very surprised if there is one and it should not be hard to prove by exhaustion. Do you allow $1$ for a ones digit because $1$ is not prime? In any case, you can do a tree search. $7$ can be extended by $1,3,4,6,9$. Now try to extend each of those and see what is left. $\endgroup$ – Ross Millikan Jun 17 at 4:33
$\begingroup$ I've seen a Numberphile video recently about truncatable primes. What you're looking for is if there is a largest left-truncatable prime or not. $\endgroup$ – Raskolnikov Jun 17 at 5:59
$\begingroup$ @Raskolnikov This is a bit different than a left-truncatable prime since OP allows starting with, for example, prime number $127$, which won't be found among left-truncatable primes since $27$ is not prime. If OP were allowing only starting with one digit primes, then the solution would be the largest left-truncatable prime in number base 10, and that is $357686312646216567629137$ having $24$ digits, according to the wikipedia and OEIS entry. That was most likely proved via an exhaustive search, since all possible left-truncatable primes in base 10 are known. $\endgroup$ – Vepir Jun 17 at 7:22
$\begingroup$ @Peter Actually it is conjectured that there are infinitely many deletable primes (in the stricter version) , which would imply (using Kőnig's lemma) that it is possible to not reach a dead end. $\endgroup$ – Robert Israel Jun 17 at 16:56
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$ ?
edited Jun 17 at 14:51
VepirVepir
$\begingroup$ Note: Among first $10^5$ primes (All primes $\lt 1.3\cdot10^6$), Only one has $m=23$, only one has $m=22$ (The second such appearing around $5.9\cdot10^5$), only five have $m=21$ and only eleven have $m=20$, making primes that have $m\ge 20$ very rare ($18$ out of first $10^5$). $\endgroup$ – Vepir Jun 17 at 18:06
$\begingroup$ (See also comments to Peter Taylor's answer.) I found it online! On https://www.primepuzzles.net/puzzles/puzz_131.htm (near bottom of page) they found that 76922083307 can be extended 24 times into the prime 96842946512633189183337876922083307. So go for even higher records now if we can. Edit: They give a reference that it was published in 1977, see On Truncatable Primes by I. O. Angell and H. J. Godwin. $\endgroup$ – Jeppe Stig Nielsen Jun 18 at 7:15
$\begingroup$ Sorry, I misread the puzzle web page. The $m=24$ example was not found in 1977 by Angell and Godwin, it is a newer discovery. $\endgroup$ – Jeppe Stig Nielsen Jun 18 at 7:23
$\begingroup$ From the puzzle page: As a matter of fact Rubin makes the following puzzling statements about this kind of objects: 1) "no matter what prime you start with and what digits you append each such sequence always ends. That is, there comes a point where there is no digit that can be appended to form another prime." Is there a proof? $\endgroup$ – JollyJoker Jun 18 at 8:29
$\begingroup$ @JeppeStigNielsen, if we look at $d$-digit primes for $d < 9$ and compute the average number of extensions to compare with my heuristic estimate, the values obtained for the constant $O(1)$ are (to two decimal places) $18, 10.14, 10.27, 9.83, 9.83, 9.75, 9.69, 9.65$. Plugging in a round value of $9$ and correcting the initial $\pi(10^d)$ to $\pi(10^d) - \pi(10^{d-1})$ I get an estimated $1.08$ $11$-digit survivors of order $24$. I'd expect to see a couple of $13$-digit survivors of order $25$, but I don't have the computational resources to test that in a reasonable time. $\endgroup$ – Peter Taylor Jun 19 at 10:13
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$.
Peter TaylorPeter Taylor
$\begingroup$ "The probability that n is prime is ..." - isn't that the probability that a random integer is prime? Trying to specifically construct only 1 single integer is most certainly not random. $\endgroup$ – Dukeling Jun 17 at 18:27
$\begingroup$ In binary numbers, we have Cunningham chains of the first kind. If we start from some prime number $p_1$ (that you can think of as written in binary), then we step up to $p_2=2p_1+1$, and in general in the chain $p_{i+1}=2p_i+1$. Each of these steps can be thought of as appending another 1-bit at the right end of the binary expansion of the previous prime. With binary, we have only one choice of digit to add. Still the link says it is conjectured that the set of lengths ("orders") is unbounded! How does that agree with your heuristics? $\endgroup$ – Jeppe Stig Nielsen Jun 17 at 19:54
$\begingroup$ @Dukeling, for very small candidate divisors we have special knowledge (I mentioned divisibility by 3; clearly divisibility by 2 and 5 are also completely classified, and if you want you can analyse more carefully for specific small primes. For larger primes we don't really have much information. The $O(1)$ could be made more precise with more effort. Also, I'm actually averaging over a lot of integers, not 1 single integer. If there were strong correlations which blew a hole in that estimate, I'd expect that a better mathmatician than me would have disproven the Riemann hypothesis with them. $\endgroup$ – Peter Taylor Jun 17 at 22:18
$\begingroup$ @JeppeStigNielsen, I don't see a disagreement. For any given finite $m$ you can pick a large enough $d$ and a pessimistic value for the constant hidden by $O(1)$ such that the heuristic suggests we should expect multiple $d$-digit survivors of order $m$. That doesn't mean that there will be a finite $d$ for which we expect a survivor of infinite order. $\endgroup$ – Peter Taylor Jun 17 at 22:22
$\begingroup$ @JeppeStigNielsen My computations are just for "small enough" primes. Even though we have less prime extensions and lower average of $m$ as primes grow, the overall maximal m could still keep breaking records for some very large primes. I wanted to find first such $m$ that would break the the initial record and have $m>23$, but looks like we need to go much beyond $10^6$ primes if we want to find the first such example. $\endgroup$ – Vepir Jun 18 at 6:02
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$.
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.
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$.
answered Jun 18 at 0:09
Erin CarmodyErin Carmody
$\begingroup$ I do not understand all the steps, so what are the assumptions you need to assume to guarantee that there is a $\infty$-survivor? $\endgroup$ – Grešnik Jun 25 at 8:18
$\begingroup$ The assumption is that there are a lot of large primes which are a concatenation of primes - this is the first part. Then, use Konig's lemma to get an infinite creature like this. It is not complete though. $\endgroup$ – Erin Carmody Jun 26 at 11:01
$\begingroup$ Can you quantify precisely the meaning of "a lot"? $\endgroup$ – Grešnik Jun 26 at 11:05
$\begingroup$ Yes, you are now aware of what I was thinking of, I think. $\endgroup$ – Grešnik Jun 26 at 15:28
$\begingroup$ You could be interested in this question of mine: math.stackexchange.com/questions/3271669/… $\endgroup$ – Grešnik Jun 27 at 8:27
Not the answer you're looking for? Browse other questions tagged elementary-number-theory prime-numbers recreational-mathematics decimal-expansion or ask your own question.
Prime number construction game
Are there primes of every possible number of digits?
Does there exist a power-summer of order $+ \infty$?
Prime from mirror concatenation of first primes
Consecutive prime numbers multiplication pattern
Conjecture on concatenation of twin prime numbers
Question on Concatenation of Prime Numbers
Are Complete Sequences Also Sets with Distinct Subset Sums? (Prime Numbers)
Longest prime containing primes
Primes formed by concatenating the mersenne numbers from $2^2-1$ to $2^n-1$
Algorithm to find prime numbers
Number 2 hasn't got this property, while all prime numbers do.
1-concatenable primes