A344129 - OEIS

%I #14 Jun 16 2021 21:02:25

%S 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,

%T 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,

%U 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

%N 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.

%e The board is numbered with the square spiral:

%e .

%e   17--16--15--14--13   .

%e    |               |   .

%e   18   5---4---3  12  29

%e    |   |       |   |   |

%e   19   6   1---2  11  28

%e    |   |           |   |

%e   20   7---8---9--10  27

%e    |                   |

%e   21--22--23--24--25--26

%e .

%e a(1) = 0 as the knight starts at the central square numbered 1.

%e 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.

%e 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.

%e 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.

%e 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.

%o (Python) # uses get_coordinate(n) in A296030

%o KM=[(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]

%o def next_moves(i, j): return [(i+k, j+m) for k, m in KM]

%o def a(n):

%o     start, goal, steps = (0, 0), get_coordinate(n), 0

%o     reach, expand = {start}, {start}

%o     while goal not in reach:

%o         reach1 = set(m for i, j in expand for m in next_moves(i, j))

%o         expand = reach1 - reach

%o         steps, reach, reach1 = steps + 1, reach | reach1, set()

%o     return steps

%o print([a(n) for n in range(1, 101)]) # _Michael S. Branicky_, Jun 15 2021

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

%K nonn

%O 1,2

%A _Scott R. Shannon_, May 10 2021