All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 How far can you go? (Posted on 2011-03-04)
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?

 No Solution Yet Submitted by Ady TZIDON Rating: 4.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 5 of 11 |

10    dim Used(9),Hist(10)
15    open "howfar.txt" for output as #2
60    print:print Ct
70    end
80
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
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

 Search: Search body:
Forums (0)