409 is an interesting prime number. If you remove any number of its digits, then you will get a number that is not prime.

4=2^2
0=not prime
9=3^2
40=2^3*5
49=7^2
09=9=3^2

Call a number with this property a minimal prime. Find all minimal primes.

(In reply to of course it also inspires a computer program by Charlie)

... and of course that could be put into a loop to find the minimal primes. However, the below program took almost half an hour to get to the highest one, and there was no way for it to determine that it was in fact the last. Further, the ones up to six digits took only a few seconds, so if one didn't know there were more one might have given up and stopped the program prematurely. Even though the primes get farther apart as you go up in scale, the individual primes take longer to check out for minimality as they get bigger.

But of course I had thought my manual solution had come up with all of them, and it had missed one. And not only that, but now (in edit after posting) I've read Math Man's comment and I see I missed another, while accepting a non-minimal.

    5     Tst=""
   10     repeat
   20       Tst=nxtprm(val(Tst)):Tst=cutspc(str(Tst))
   30       Pr=""
   40       Good=1
   50       if prmdiv(val(Tst))<val(Tst) then Good=0:else gosub *Testing(1)
   60       if Good then print Tst
   65     until Tst="0"
   70       end
   80
   90       *Testing(Psn)
  100       if Psn=len(Tst) then
  110         :Prtst=val(Pr)
  120         :if prmdiv(Prtst)=Prtst and Prtst<>0 and Prtst<>1 then Good=0:endif
  130       :else
  140         :gosub *Testing(Psn+1)
  150       Pr=Pr+mid(Tst,Psn,1)
  160       if Psn=len(Tst) and Psn>len(Pr) then
  170         :Prtst=val(Pr)
  180         :if prmdiv(Prtst)=Prtst and Prtst<>0 and Prtst<>1 then Good=0:endif
  190       if Psn<len(Tst) then
  200         :gosub *Testing(Psn+1)
  205       Pr=left(Pr,len(Pr)-1)
  210       return

Edited on April 24, 2012, 5:30 pm

Posted by Charlie on 2012-04-24 17:28:34