2
$\begingroup$

We say that the (base ten) prime number $p=a_{n}a_{n-1}a_{n-2}\cdots a_{1}a_{0}$ is right-truncatable if all of the following numbers are prime: \begin{eqnarray*}a_{n},\\a_{n}a_{n-1},\\ a_{n}a_{n-1}a_{n-2},\\ \vdots\\ a_{n}a_{n-1}a_{n-2} \cdots a_{1}.\end{eqnarray*}

According to user David W. Wilson of the OEIS, there exist only $83$ right-truncatable prime numbers: Mr. D. W. Wilson also claims that the largest such prime is $73 \, 939 \, 133$. Since the first of these two claims provides a clear-cut answer to a problem which I had come up with some time ago (before I even knew these primes were called right-truncatable; in point of fact, I had christened 'em as totally prime (go figure!)), I would like to know if you know of (or can supply) a non-computer-assisted straightforward proof of the finiteness of the set of right-truncatable prime numbers...

It may be mentioned that, in order to test those two assertions of Mr. D. W. Wilson, I wrote a Mathematica program that determines whether or not a given prime number is right-truncatable and had it look for primes of that type in the interval $[10^{8}, 10^{9})$:

For[k = 100000000, k < 1000000000, k++,
If[PrimeQ[k],
aux = 1;
flag = 2;
j = k;
While[flag <= IntegerLength[j], h = (j - Mod[j, 10])/10;
If[PrimeQ[h], aux = aux + 1; j = h; flag = flag - 1, flag = 1000]];
If[aux == IntegerLength[k], Print[k]];
]]

As any die-hard fan of the OEIS would have expected, the above program found no right-truncatable prime number in that interval!

Please, let me thank you in advance for your knowledgeable replies.

$\endgroup$
9
  • 3
    $\begingroup$ Wouldn't it be very easy to write a program that goes along a tree starting with $3$ or $7$, and at each stage adding $1$, $3$, $7$, $9$ on the right if that number continues to be prime? I know you asked for a non-computer proof, but why would one do that for what seems an obviously (fun) computational problem? $\endgroup$
    – Lucia
    May 6, 2016 at 5:11
  • 2
    $\begingroup$ I can supply a non-computer-assisted straightforward proof for base 2.... $\endgroup$ May 6, 2016 at 6:44
  • 2
    $\begingroup$ Maybe the non-computer-assisted proof the OP desires will prove the finiteness in all bases. Your computer search may choke on that. $\endgroup$ May 6, 2016 at 17:55
  • 2
    $\begingroup$ Building the tree should not require a computer. Since we are told there are only 83 primes in the tree, proving this will only take $4\times83=332$ or so cases, which is perfectly doable by hand, even if tedious. $\endgroup$ May 6, 2016 at 18:06
  • 1
    $\begingroup$ Heuristically it would be surprising if there were an infinite number: if there are $k$ $d$-digit right truncatable primes, we expect about $4k / (d \log 10)$ $(d+1)$-digit primes. $\endgroup$ Jun 30, 2021 at 22:13

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.