A superprime is an integer such that all its left-to-right initial segments are prime (e.g. 7331 whose segments are 7, 73, 733, and 7331, all prime).
There is a largest superprime.

Find it.

Source: USA Computing Olympiad, Feb 1995.

The following program finds all the superprimes recursively, and reports each new highest one it finds.

list
   10     Pr=2:gosub *Addon
   20     Pr=3:gosub *Addon
   30     Pr=5:gosub *Addon
   40     Pr=7:gosub *Addon
   50     end
   60
   70     *Addon
   75     local Dig
   80     for Dig=1 to 9 step 2
   90       Pr=Pr*10+Dig
  100       if prmdiv(Pr)=Pr then
  110       :if Pr>Max then print Pr:Max=Pr:endif
  120       :gosub *Addon
  130       if prmdiv(Pr)=0 then print "**":end
  140       Pr=Pr\10
  150     next Dig
  160     return
OK
run
 23
 233
 2333
 23333
 23339
 23399
 233993
 2339933
 23399339
 29399999
 37337999
 59393339
 73939133
OK

The last highest one is 73939133 and so that is the answer.

All the superprimes are listed below:

 23333
 23339
 23399339
 2393
 2399333
 29399999
 31193
 31379
 317
 37337999
 373393
 37397
 3793
 3797
 53
 59393339
 593993
 599
 719333
 7331
 73331
 73939133
 7393931
 7393933
 739397
 739399
 797
 
 Note that some are included only as the leading subset of their longest containing superprime, such as 71, 719, 7193, etc. being covered by the entry 719333.
 
 This list was produced by the following program, with duplicates, including those mentioned in the preceding paragraph, manually excluded.

   5   open "suprprim.txt" for output as #2
  10     Pr=2:gosub *Addon
  20     Pr=3:gosub *Addon
  30     Pr=5:gosub *Addon
  40     Pr=7:gosub *Addon
  50     end
  60
  70     *Addon
  75     local Dig
  80     for Dig=1 to 9 step 2
  90       Pr=Pr*10+Dig
 100       if prmdiv(Pr)=Pr then
 120       :gosub *Addon
 125       :else print #2,Pr\10
 130       if prmdiv(Pr)=0 then print "**":end
 140       Pr=Pr\10
 150     next Dig
 160     return
 170   close 2
 
 

Posted by Charlie on 2010-10-20 14:17:12