A344129 The minimum number of steps required for a knight, starting at the central square numbered 1, to reach the square numbered n on a square-spiral numbered board.

0, 3, 2, 3, 2, 3, 2, 3, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 2, 3, 4, 3, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3

Offset

1,2

Links

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

Example

The board is numbered with the square spiral:
.
  17--16--15--14--13   .
   |               |   .
  18   5---4---3  12  29
   |   |       |   |   |
  19   6   1---2  11  28
   |   |           |   |
  20   7---8---9--10  27
   |                   |
  21--22--23--24--25--26
.
a(1) = 0 as the knight starts at the central square numbered 1.
a(2) = 3 as it requires 3 steps for a knight to move to any of the four adjacent squares. An example path is 1 - 12 - 15 - 2.
a(3) = 2 as it requires 2 steps for a knight to move to any of the four diagonally adjacent squares. An example path is 1 - 10 - 3.
a(10) = 1 as the square numbered 10, along with the squares numbered 12, 14, 16, 18, 20, 22, 24, are one direct knight leap away from the starting square.
a(13) = 4 as it requires 4 steps for a knight to move to any of the four squares diagonally two squares away. An example path is 1 - 14 - 11 - 4 - 13.

Prog

(Python) # uses get_coordinate(n) in A296030
KM=[(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
def next_moves(i, j): return [(i+k, j+m) for k, m in KM]
def a(n):
    start, goal, steps = (0, 0), get_coordinate(n), 0
    reach, expand = {start}, {start}
    while goal not in reach:
        reach1 = set(m for i, j in expand for m in next_moves(i, j))
        expand = reach1 - reach
        steps, reach, reach1 = steps + 1, reach | reach1, set()
    return steps
print([a(n) for n in range(1, 101)]) # Michael S. Branicky, Jun 15 2021

Crossrefs

Cf. A296030, A174344, A274923, A344046, A316667.

Sequence in context: A245219 A097509 A095206 * A308006 A049071 A168330

Adjacent sequences: A344126 A344127 A344128 * A344130 A344131 A344132

Keyword

nonn

Author

Scott R. Shannon, May 10 2021

Status

approved