How many numbers, from 1 to 50 (both included) can you arrange in a row (one of each) so that each one, except the first and the last, is the sum or difference of its two neighbours?

Example: 3, 10, 7, 17, 24, 41.

10 = 3+7, 7 = 17-10, 17 = 24-7, 24 = 41-17.

The equivalent description of he sequence is that, except for the first two, each successive number is either the sum or difference of the two preceding numbers.  The program below uses that fact and could be modified by using the absolute value of the difference, but that's in hindsight; as is, it takes the difference in each direction separately, as the wording of the problem tends to make one think those are different categories.

DECLARE SUB place (n!)
CLEAR , , 25000

DIM SHARED highNum
highNum = 50
DIM SHARED used(highNum), h(highNum), max

FOR i = 1 TO highNum
 h(1) = i
 used(i) = 1
 FOR j = 1 TO highNum
   IF used(j) = 0 THEN
    h(2) = j
    used(j) = 1
    place 3
    used(j) = 0
   END IF
 NEXT
 used(i) = 0
NEXT

SUB place (n)
  dead = 1
  sum = h(n - 2) + h(n - 1)
  IF sum <= highNum THEN
    IF used(sum) = 0 THEN
      h(n) = sum
      used(sum) = 1
      place n + 1
      used(sum) = 0
      dead = 0
    END IF
  END IF
  diff = h(n - 2) - h(n - 1)
  IF diff > 0 THEN
    IF used(diff) = 0 THEN
      h(n) = diff
      used(diff) = 1
      place n + 1
      used(diff) = 0
      dead = 0
    END IF
  END IF
  diff = h(n - 1) - h(n - 2)
  IF diff > 0 THEN
    IF used(diff) = 0 THEN
      h(n) = diff
      used(diff) = 1
      place n + 1
      used(diff) = 0
      dead = 0
    END IF
  END IF
  IF dead THEN
   IF n >= max THEN
     FOR i = 1 TO n - 1
      PRINT h(i);
     NEXT
     PRINT TAB(70); n - 1
     max = n
   END IF
  END IF
END SUB

The longest sequence found has 13 members. It's unique except for reversal:

41  25  16  9  7  2  5  3  8  11  19  30  49
49  30  19  11  8  3  5  2  7  9  16  25  41

Posted by Charlie on 2008-11-20 17:21:55