Truncatable Primes

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:

cat3prime:= proc(n)
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;
end proc;

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

This entry was posted in Number Theory. Bookmark the permalink.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>