# Is there a largest “nested” prime number?

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?

-

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).

-

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.$

-
Has this been proven to be the largest such prime? –  Alex Becker Sep 26 '12 at 2:08
I presume so. It would be easy to check-you just need to prefix this number with each of $2,3,5,$ and $7$ and see that none are prime. –  Ross Millikan Sep 26 '12 at 2:10
I think you'd also need to check other 8-digit primes on the list, but good point. –  Alex Becker Sep 26 '12 at 2:11
@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. –  Ross Millikan Sep 26 '12 at 2:20