1
$\begingroup$

There are some prime numbers which I will call "nested primes" that have a curious property: if the $n$ digit prime number $p$ is written out in base 10 notation $p=d_1d_2...d_n$, then the nested sequence formed by deleting the last digit one at a time consists entirely of prime numbers. The definition is best illustrated by an example, for which I will choose the number $3733799$: not only is $3733799$ prime, but so are $\{3,37,373,3733,37337,373379\}$. See here and here if you want to check.

Question: Does there exist a largest nested prime number, and if so, what is it?

2 Answers 2

1

Here's some GAP code which exhaustively enumerates all nested primes. It's a backtracking algorithm, adding a new digit at each step. It the current number is a prime, it prints it out, otherwise, throws it away.

DigitsToInt:=function(d)   return Sum([1..Size(d)],i->10^(Size(d)-i)*d[i]); end;;  NestPrime:=function(d)   local i,k;   for i in [1,3,7,9] do     d:=Concatenation(d,[i]);     k:=DigitsToInt(d);     if(IsPrimeInt(k)) then       Print(k,"\n");       NestPrime(d);     fi;     d:=List([1..Size(d)-1],j->d[j]);   od; end;;  for d in [[2],[3],[5],[7]] do   k:=DigitsToInt(d);   Print(k,"\n");   NestPrime(d); od; 

Note that GAP's IsPrimeInt is a deterministic primality test for $n \leq 10^{13}$, which is sufficient in this case.

Which outputs:

2 23 233 2333 23333 23339 2339 23399 233993 2339933 23399339 239 2393 2399 23993 239933 2399333 29 293 2939 29399 293999 2939999 29399999 3 31 311 3119 31193 313 3137 31379 317 37 373 3733 37337 373379 3733799 37337999 37339 373393 3739 37397 379 3793 3797 5 53 59 593 5939 59393 593933 5939333 59393339 59399 593993 599 7 71 719 7193 71933 719333 73 733 7331 7333 73331 739 7393 73939 739391 7393913 73939133 739393 7393931 7393933 739397 739399 79 797 

So, yes there is a largest nested prime, and it's 73939133 (in agreement with Ross Millikan's answer and Sloane's A024770).

2

From the comments in OEIS A024770

Primes in which repeatedly deleting the least significant digit gives a prime at every step until a single digit prime remains. The sequence ends at $a(83) = 73939133.$

  • 0
    @AlexBecker: correct. I hadn't checked, but there are other 8 digit numbers. Only the last three need to be checked, as the first two start with 2, which can't be the last digit of a 2 digit prime.2012-09-26