Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #21 Dec 05 2019 20:34:54
%S 1,6,15,4,12,8,12,4,9,10,16,18,25,28,27,14,32,18,16,36,21,30,49,54,64,
%T 70,81,88,100,108,121,108,91,90,85,76,63,92,125,78,56,90,128,102,144,
%U 102,64,90,112,130,144,154,160,162,160,154,169,180,196
%N A chess knight starts at 1 on an extended multiplication table and moves to the next perfect power such that 1) the number of jumps is minimized and 2) the sum of the intermediate numbers is minimized. In case of a tie, choose the lexicographically earliest path.
%e Between 4 and 8, the shortest route is through 12 (2*6); it takes only two steps:
%e .
%e 1 2 3 4 5 6 7 8
%e +------+------+------+------+------+------+------+------+
%e | | | | | | | | |
%e 1 | 1 | 2 | 3 | *4* | 5 | 6 | 7 | .*8* |
%e | | | | |. | | . | |
%e +------+------+------+------+---.--+------+-.----+------+
%e | | | | | . .| | |
%e 2 | 2 | 4 | 6 | 8 | 10 | *12* | 14 | 16 |
%e | | | | | | | | |
%e +------+------+------+------+------+------+------+------+
%e | | | | | | | | |
%e 3 | 3 | 6 | 9 | 12 | 15 | 18 | 21 | 24 |
%e | | | | | | | | |
%e +------+------+------+------+------+------+------+------+
%e | | | | | | | | |
%e 4 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 |
%e | | | | | | | | |
%e +------+------+------+------+------+------+------+------+
%e .
%e Between 32 and 36, there are several routes that take only three jumps. We choose 32,18,16,36 because the sum of intermediate numbers is the least.
%Y Cf. A316588, A316328.
%K nonn
%O 1,2
%A _Ali Sada_, Dec 02 2019