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 [,,,] 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