A colleague asked about sequences of primes a(n) such that a(n+1) is obtained by appending a single digit (in base 10) to the right of a(n).
For example: 3, 31, 311 …
Some thinking lead to the conjecture that such sequences are of finite length and that it is possible to use an exhaustive search to find all of them. A natural question would be what is the longest possible sequence but I was unable to find any conclusive answer on the web. So I decided to write a simple (and not very efficient) recursion in maple to search for all such primes. Here’s my ugly code:
local d, s, i; s:=n; d:=irem(n,10);
if isprime(s) then print(s); return(cat3prime(10*s+1));
else for i from d to 7 by 2 do
if isprime(s-d+i+2) then s:=s-d+i+2; print(s); return cat3prime(10*s+1); fi; od;
while (irem(s,10)=9) do s:=(s-9)/10; od;
if s=0 then return print(“search complete”);
else return cat3prime(s+2); fi; fi;
The search yielded five sequences of length 8 and no other longer sequences:
Only one of the above sequences appears as is on OEIS but with a more careful search, I found a sequence called right-truncatable primes.
Which contains 83 primes, where successively truncating one digit from the right still results in a prime. I verified that my own maple search also yielded 83 primes and I guess the two lists must be identical. See the wikipedia entry on truncatable primes https://en.wikipedia.org/wiki/Truncatable_prime