Starting with a prime digit add another digit, after or before the first, then another, adding it after, before or within the second number, and continue, keeping the resulting numbers prime, without repeating any of the digits you have used so far.

Example: 2, 23, 263, 2063, 29063....

Obviously you cannot reach a pandigital number (it will always be divisible by 9) .

What are the lowest and highest numbers in the set of eligible solutions with the maximum number of digits?

Please specify the interim stages leading to your results.

   10    dim Used(9),Hist(10)
   15    open "howfar.txt" for output as #2
   20    S="2":Used(2)=1:gosub *AddOn:Used(2)=0
   30    S="3":Used(3)=1:gosub *AddOn:Used(3)=0
   40    S="5":Used(5)=1:gosub *AddOn:Used(5)=0
   50    S="7":Used(7)=1:gosub *AddOn:Used(7)=0
   60    print:print Ct
   70    end
   80  
   90    *AddOn
  100    local Ps,Dig,Stdig,Ssave,Hadone,I
  109    Hadone=0
  110    for Ps=0 to len(S)
  120      for Dig=0 to 9
  122        Good=1
  124        if S="2" and (Dig=3 or Dig=5 or Dig=7) or S="3" and (Dig=5 or Dig=7) or S="5" and Dig=7 then Good=0
  130        if Used(Dig)=0 and Good=1 then
  140         :Used(Dig)=1
  150         :Nc=cutspc(str(Dig))
  160         :S2=left(S,Ps)+Nc+mid(S,Ps+1,*)
  170         :if prmdiv(val(S2))=val(S2) then
  175          :Ssave=S
  176          :S=S2
  180          :PrPend=1
  182          :Hist(len(S))=S
  190          :gosub *AddOn:Hadone=1
  200          :S=Ssave
  210         :endif
  220         :Used(Dig)=0
  230      next Dig
  240    next Ps
  245    if PrPend=1 and Hadone=0 then
  250      :PrPend=0:Ct=Ct+1
  260      :for I=2 to len(S)
  270       :print Hist(I);" ";
  275       :print #2,Hist(I);" ";
  280      :next I:print:print #2,
  290    return
 
found over 1.5 million sequences, as it eliminates some initial pairs such as 2 to which a 3 was then attached, in favor of keeping 3 with a 2 attached, as each is 23 at the stage of having two digits, which is the stage at which the reporting begins (see below).

The resulting file was then sorted on the columns with the 9-digit strings, which is the maximum length.

The lowest number produced with this maximum number of digits is 102345697 if leading zeros are not allowed, but 012345769 if they are.

13 137 1367 13567 103567 1034567 10345697 102345697
17 107 1097 10597 104597 1034597 10345697 102345697
17 137 1367 13567 103567 1034567 10345697 102345697
17 157 1567 10567 103567 1034567 10345697 102345697
17 157 1567 13567 103567 1034567 10345697 102345697
17 157 1597 10597 104597 1034597 10345697 102345697
17 157 1597 13597 134597 1034597 10345697 102345697
17 167 1367 13567 103567 1034567 10345697 102345697
17 167 1567 10567 103567 1034567 10345697 102345697
17 167 1567 13567 103567 1034567 10345697 102345697
17 197 1097 10597 104597 1034597 10345697 102345697
17 197 1597 10597 104597 1034597 10345697 102345697
17 197 1597 13597 134597 1034597 10345697 102345697
37 137 1367 13567 103567 1034567 10345697 102345697
37 347 3457 13457 103457 1034567 10345697 102345697
37 347 3457 13457 103457 1034597 10345697 102345697
37 347 3457 13457 134597 1034597 10345697 102345697
37 367 1367 13567 103567 1034567 10345697 102345697
47 347 3457 13457 103457 1034567 10345697 102345697
47 347 3457 13457 103457 1034597 10345697 102345697
47 347 3457 13457 134597 1034597 10345697 102345697
47 457 3457 13457 103457 1034567 10345697 102345697
47 457 3457 13457 103457 1034597 10345697 102345697
47 457 3457 13457 134597 1034597 10345697 102345697
67 167 1367 13567 103567 1034567 10345697 102345697
67 167 1567 10567 103567 1034567 10345697 102345697
67 167 1567 13567 103567 1034567 10345697 102345697
67 367 1367 13567 103567 1034567 10345697 102345697
97 197 1097 10597 104597 1034597 10345697 102345697
97 197 1597 10597 104597 1034597 10345697 102345697
97 197 1597 13597 134597 1034597 10345697 102345697

Lines with leading zeros were deleted manually from the above.

03 013 0137 01237 012347 0123479 01234769 012345769
03 013 0137 01237 012379 0123479 01234769 012345769
03 037 0137 01237 012347 0123479 01234769 012345769
03 037 0137 01237 012379 0123479 01234769 012345769
03 037 0347 02347 012347 0123479 01234769 012345769
07 017 0127 01237 012347 0123479 01234769 012345769
07 017 0127 01237 012379 0123479 01234769 012345769
07 017 0127 01279 012379 0123479 01234769 012345769
07 017 0127 01279 012479 0123479 01234769 012345769
07 017 0127 01279 012479 0124769 01234769 012345769
07 017 0137 01237 012347 0123479 01234769 012345769
07 017 0137 01237 012379 0123479 01234769 012345769
07 017 0179 01279 012379 0123479 01234769 012345769
07 017 0179 01279 012479 0123479 01234769 012345769
07 017 0179 01279 012479 0124769 01234769 012345769
07 037 0137 01237 012347 0123479 01234769 012345769
07 037 0137 01237 012379 0123479 01234769 012345769
07 037 0347 02347 012347 0123479 01234769 012345769
07 047 0347 02347 012347 0123479 01234769 012345769
07 079 0179 01279 012379 0123479 01234769 012345769
07 079 0179 01279 012479 0123479 01234769 012345769
07 079 0179 01279 012479 0124769 01234769 012345769
13 013 0137 01237 012347 0123479 01234769 012345769
13 013 0137 01237 012379 0123479 01234769 012345769
13 137 0137 01237 012347 0123479 01234769 012345769
13 137 0137 01237 012379 0123479 01234769 012345769
13 137 1237 01237 012347 0123479 01234769 012345769
13 137 1237 01237 012379 0123479 01234769 012345769
13 137 1237 12347 012347 0123479 01234769 012345769
13 137 1237 12347 123479 0123479 01234769 012345769
13 137 1237 12347 123479 1234769 01234769 012345769
13 137 1237 12347 123479 1234769 12345769 012345769
13 137 1237 12379 012379 0123479 01234769 012345769
13 137 1237 12379 123479 0123479 01234769 012345769
13 137 1237 12379 123479 1234769 01234769 012345769
13 137 1237 12379 123479 1234769 12345769 012345769
17 017 0127 01237 012347 0123479 01234769 012345769
17 017 0127 01237 012379 0123479 01234769 012345769
17 017 0127 01279 012379 0123479 01234769 012345769
17 017 0127 01279 012479 0123479 01234769 012345769
17 017 0127 01279 012479 0124769 01234769 012345769
17 017 0137 01237 012347 0123479 01234769 012345769
17 017 0137 01237 012379 0123479 01234769 012345769
17 017 0179 01279 012379 0123479 01234769 012345769
17 017 0179 01279 012479 0123479 01234769 012345769
17 017 0179 01279 012479 0124769 01234769 012345769
17 127 0127 01237 012347 0123479 01234769 012345769
17 127 0127 01237 012379 0123479 01234769 012345769
17 127 0127 01279 012379 0123479 01234769 012345769
17 127 0127 01279 012479 0123479 01234769 012345769
17 127 0127 01279 012479 0124769 01234769 012345769
17 127 1237 01237 012347 0123479 01234769 012345769
17 127 1237 01237 012379 0123479 01234769 012345769
17 127 1237 12347 012347 0123479 01234769 012345769
17 127 1237 12347 123479 0123479 01234769 012345769
17 127 1237 12347 123479 1234769 01234769 012345769
17 127 1237 12347 123479 1234769 12345769 012345769
17 127 1237 12379 012379 0123479 01234769 012345769
17 127 1237 12379 123479 0123479 01234769 012345769
17 127 1237 12379 123479 1234769 01234769 012345769
17 127 1237 12379 123479 1234769 12345769 012345769
17 127 1279 01279 012379 0123479 01234769 012345769
17 127 1279 01279 012479 0123479 01234769 012345769
17 127 1279 01279 012479 0124769 01234769 012345769
17 127 1279 12379 012379 0123479 01234769 012345769
17 127 1279 12379 123479 0123479 01234769 012345769
17 127 1279 12379 123479 1234769 01234769 012345769
17 127 1279 12379 123479 1234769 12345769 012345769
17 127 1279 12479 012479 0123479 01234769 012345769
17 127 1279 12479 012479 0124769 01234769 012345769
17 127 1279 12479 123479 0123479 01234769 012345769
17 127 1279 12479 123479 1234769 01234769 012345769
17 127 1279 12479 123479 1234769 12345769 012345769
17 127 1279 12479 124769 0124769 01234769 012345769
17 127 1279 12479 124769 1234769 01234769 012345769
17 127 1279 12479 124769 1234769 12345769 012345769
17 137 0137 01237 012347 0123479 01234769 012345769
17 137 0137 01237 012379 0123479 01234769 012345769
17 137 1237 01237 012347 0123479 01234769 012345769
17 137 1237 01237 012379 0123479 01234769 012345769
17 137 1237 12347 012347 0123479 01234769 012345769
17 137 1237 12347 123479 0123479 01234769 012345769
17 137 1237 12347 123479 1234769 01234769 012345769
17 137 1237 12347 123479 1234769 12345769 012345769
17 137 1237 12379 012379 0123479 01234769 012345769
17 137 1237 12379 123479 0123479 01234769 012345769
17 137 1237 12379 123479 1234769 01234769 012345769
17 137 1237 12379 123479 1234769 12345769 012345769
17 179 0179 01279 012379 0123479 01234769 012345769
17 179 0179 01279 012479 0123479 01234769 012345769
17 179 0179 01279 012479 0124769 01234769 012345769
17 179 1279 01279 012379 0123479 01234769 012345769
17 179 1279 01279 012479 0123479 01234769 012345769
17 179 1279 01279 012479 0124769 01234769 012345769
17 179 1279 12379 012379 0123479 01234769 012345769
17 179 1279 12379 123479 0123479 01234769 012345769
17 179 1279 12379 123479 1234769 01234769 012345769
17 179 1279 12379 123479 1234769 12345769 012345769
17 179 1279 12479 012479 0123479 01234769 012345769
17 179 1279 12479 012479 0124769 01234769 012345769
17 179 1279 12479 123479 0123479 01234769 012345769
17 179 1279 12479 123479 1234769 01234769 012345769
17 179 1279 12479 123479 1234769 12345769 012345769
17 179 1279 12479 124769 0124769 01234769 012345769
17 179 1279 12479 124769 1234769 01234769 012345769
17 179 1279 12479 124769 1234769 12345769 012345769
37 037 0137 01237 012347 0123479 01234769 012345769
37 037 0137 01237 012379 0123479 01234769 012345769
37 037 0347 02347 012347 0123479 01234769 012345769
37 137 0137 01237 012347 0123479 01234769 012345769
37 137 0137 01237 012379 0123479 01234769 012345769
37 137 1237 01237 012347 0123479 01234769 012345769
37 137 1237 01237 012379 0123479 01234769 012345769
37 137 1237 12347 012347 0123479 01234769 012345769
37 137 1237 12347 123479 0123479 01234769 012345769
37 137 1237 12347 123479 1234769 01234769 012345769
37 137 1237 12347 123479 1234769 12345769 012345769
37 137 1237 12379 012379 0123479 01234769 012345769
37 137 1237 12379 123479 0123479 01234769 012345769
37 137 1237 12379 123479 1234769 01234769 012345769
37 137 1237 12379 123479 1234769 12345769 012345769
37 347 0347 02347 012347 0123479 01234769 012345769
37 347 2347 02347 012347 0123479 01234769 012345769
37 347 2347 12347 012347 0123479 01234769 012345769
37 347 2347 12347 123479 0123479 01234769 012345769
37 347 2347 12347 123479 1234769 01234769 012345769
37 347 2347 12347 123479 1234769 12345769 012345769
47 047 0347 02347 012347 0123479 01234769 012345769
47 347 0347 02347 012347 0123479 01234769 012345769
47 347 2347 02347 012347 0123479 01234769 012345769
47 347 2347 12347 012347 0123479 01234769 012345769
47 347 2347 12347 123479 0123479 01234769 012345769
47 347 2347 12347 123479 1234769 01234769 012345769
47 347 2347 12347 123479 1234769 12345769 012345769
79 079 0179 01279 012379 0123479 01234769 012345769
79 079 0179 01279 012479 0123479 01234769 012345769
79 079 0179 01279 012479 0124769 01234769 012345769
79 179 0179 01279 012379 0123479 01234769 012345769
79 179 0179 01279 012479 0123479 01234769 012345769
79 179 0179 01279 012479 0124769 01234769 012345769
79 179 1279 01279 012379 0123479 01234769 012345769
79 179 1279 01279 012479 0123479 01234769 012345769
79 179 1279 01279 012479 0124769 01234769 012345769
79 179 1279 12379 012379 0123479 01234769 012345769
79 179 1279 12379 123479 0123479 01234769 012345769
79 179 1279 12379 123479 1234769 01234769 012345769
79 179 1279 12379 123479 1234769 12345769 012345769
79 179 1279 12479 012479 0123479 01234769 012345769
79 179 1279 12479 012479 0124769 01234769 012345769
79 179 1279 12479 123479 0123479 01234769 012345769
79 179 1279 12479 123479 1234769 01234769 012345769
79 179 1279 12479 123479 1234769 12345769 012345769
79 179 1279 12479 124769 0124769 01234769 012345769
79 179 1279 12479 124769 1234769 01234769 012345769
79 179 1279 12479 124769 1234769 12345769 012345769

The highest was 987651403:

43 643 7643 76543 765143 8765143 98765143 987651403
43 743 7643 76543 765143 8765143 98765143 987651403
71 971 9871 98713 987143 9871403 98751403 987651403
73 743 7643 76543 765143 8765143 98765143 987651403
97 971 9871 98713 987143 9871403 98751403 987651403

which at no stage involved any leading zeros.

There is a sense in which 32609 is the smallest such number of "maximal" length, as it is located at a "local maximum" of the length of the string. No other digit can be placed in or next to it and retain primality. Here are the strings that reach a block at 4 or 5 digits:

73 739 7639 70639
73 739 7039 70639
53 653 0653
03 053 0653
53 053 0653
05 053 0653
29 269 2609 32609
79 709 7039 70639
79 709 7069 70639
79 739 7039 70639
79 739 7639 70639
79 769 7069 70639
79 769 7639 70639

It might seem that 653 is such a local maximum length, but the series above don't continue because of the zero placed at the beginning of the string. There are many continuations for 653 that extend all the way to length 9, such as for example:

53 653 6053 60539 605329 6053129 86053129 860531429
53 653 6053 60539 605329 6053129 60853129 608753129
53 653 6053 60539 605329 6053129 60853129 608573129
53 653 6053 60539 605329 6053129 60853129 608543129
53 653 6053 60539 605329 6053129 60853129 608531279
53 653 6053 60539 605329 6053129 60853129 608531249
53 653 6053 60539 605329 6053129 60531829 607531829
53 653 6053 60539 605329 6053129 60531829 605318429

To show that 32609 is a dead-end of locally maximal length, here are all the possibities for continuation, with their factorizations:

 132609 = 3*44203
 432609 = 3*144203
 532609 = 7*11*6917
 732609 = 3*3*81401
 832609 = 17*17*43*67

 312609 = 3*11*9473
 342609 = 3*114203
 352609 = 53*6653
 372609 = 3*3*19*2179
 382609 = 157*2437

 321609 = 3*23*59*79
 324609 = 3*108203
 325609 = 83*3923
 327609 = 3*3*89*409
 328609 = 347*947

 326109 = 3*7*53*293
 326409 = 3*108803
 326509 = 47*6947
 326709 = 3*3*31*1171
 326809 = 7*46687

 326019 = 3*109*997
 326049 = 3*251*433
 326059 = 19*131*131
 326079 = 3*3*3*13*929
 326089 = 31*67*157

 326091 = 3*73*1489
 326094 = 2*3*17*23*139
 326095 = 5*7*7*11*11*11
 326097 = 3*3*19*1907
 326098 = 2*103*1583

Edited on March 4, 2011, 9:02 pm

Posted by Charlie on 2011-03-04 21:00:19