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 = 1710, 17 = 247, 24 = 4117.
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 20081120 17:21:55 