4
$\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?

$\endgroup$

2 Answers 2

5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Has this been proven to be the largest such prime? $\endgroup$ Sep 26, 2012 at 2:08
  • $\begingroup$ 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. $\endgroup$ Sep 26, 2012 at 2:10
  • $\begingroup$ I think you'd also need to check other 8-digit primes on the list, but good point. $\endgroup$ Sep 26, 2012 at 2:11
  • $\begingroup$ @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. $\endgroup$ Sep 26, 2012 at 2:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .