Starting from an arbitrary prime of 3 digits you choose, construct a sequence of distinct 3-digit primes such that every one is formed by the 2 rightmost digits of the previous one plus any digit juxtaposed to the right - e.g. 113, 137, 373,... What is the maximum number of distinct primes that YOU can achieve in the sequence?

(In reply to 1820 computer solutions by Charlie)

Originally the program reported any that met or exceeded the best so far, but when that was found to be 26, was changed to match on that:

DECLARE SUB addOn (lvl!)
DATA 101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149
DATA  151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 , 211
DATA  223 , 227 , 229 , 233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277
DATA  281 , 283 , 293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 , 353
DATA  359 , 367 , 373 , 379 , 383 , 389 , 397 , 401 , 409 , 419 , 421 , 431
DATA  433 , 439 , 443 , 449 , 457 , 461 , 463 , 467 , 479 , 487 , 491 , 499
DATA  503 , 509 , 521 , 523 , 541 , 547 , 557 , 563 , 569 , 571 , 577 , 587
DATA  593 , 599 , 601 , 607 , 613 , 617 , 619 , 631 , 641 , 643 , 647 , 653
DATA  659 , 661 , 673 , 677 , 683 , 691 , 701 , 709 , 719 , 727 , 733 , 739
DATA  743 , 751 , 757 , 761 , 769 , 773 , 787 , 797 , 809 , 811 , 821 , 823
DATA  827 , 829 , 839 , 853 , 857 , 859 , 863 , 877 , 881 , 883 , 887 , 907
DATA  911 , 919 , 929 , 937 , 941 , 947 , 953 , 967 , 971 , 977 , 983 , 991
DATA 997 , end

DIM SHARED pr$(150)
DIM SHARED used(150)
DIM SHARED h$(150), noPr, best

OPEN "stringpr.txt" FOR OUTPUT AS #2

DO
 i = i + 1
 READ p$
 IF p$ <> "end" THEN
 pr$(i) = p$
 ELSE
 EXIT DO
 END IF
LOOP

noPr = i - 1

FOR i = 1 TO noPr
 h$(1) = pr$(i)
 used(i) = 1

 addOn 1

 used(i) = 0
NEXT

CLOSE

SUB addOn (lvl)
 twoChar$ = MID$(h$(lvl), 2)
 anyDone = 0
 FOR i = 1 TO noPr
  IF LEFT$(pr$(i), 2) = twoChar$ AND used(i) = 0 THEN
  
  nxtLvl = lvl + 1
  h$(nxtLvl) = pr$(i)
  used(i) = 1
  anyDone = 1

  addOn nxtLvl

  used(i) = 0

  END IF
 NEXT i

 IF anyDone = 0 AND lvl = 26 THEN
  FOR i = 1 TO lvl
   PRINT h$(i); " ";
   PRINT #2, h$(i); " ";
  NEXT
  best = lvl
  PRINT : PRINT
  PRINT #2,
 END IF
END SUB

 

Posted by Charlie on 2005-09-01 14:25:00