Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.