A327602 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.

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, 70, 81, 88, 100, 108, 121, 108, 91, 90, 85, 76, 63, 92, 125, 78, 56, 90, 128, 102, 144, 102, 64, 90, 112, 130, 144, 154, 160, 162, 160, 154, 169, 180, 196

Offset

1,2

Links

Table of n, a(n) for n=1..59.

Example

Between 4 and 8, the shortest route is through 12 (2*6); it takes only two steps:
.
      1      2      3      4      5      6      7      8
  +------+------+------+------+------+------+------+------+
  |      |      |      |      |      |      |      |      |
1 |   1  |   2  |   3  |  *4* |   5  |   6  |   7  | .*8* |
  |      |      |      |      |.     |      |    . |      |
  +------+------+------+------+---.--+------+-.----+------+
  |      |      |      |      |      .     .|      |      |
2 |   2  |   4  |   6  |   8  |  10  | *12* |  14  |  16  |
  |      |      |      |      |      |      |      |      |
  +------+------+------+------+------+------+------+------+
  |      |      |      |      |      |      |      |      |
3 |   3  |   6  |   9  |  12  |  15  |  18  |  21  |  24  |
  |      |      |      |      |      |      |      |      |
  +------+------+------+------+------+------+------+------+
  |      |      |      |      |      |      |      |      |
4 |   4  |   8  |  12  |  16  |  20  |  24  |  28  |  32  |
  |      |      |      |      |      |      |      |      |
  +------+------+------+------+------+------+------+------+
.
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.

Crossrefs

Cf. A316588, A316328.

Sequence in context: A328339 A019306 A115408 * A105052 A003566 A349083

Adjacent sequences: A327599 A327600 A327601 * A327603 A327604 A327605

Keyword

nonn

Author

Ali Sada, Dec 02 2019

Status

approved