cp's OEIS Frontend

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.

%I A344129 #14 Jun 16 2021 21:02:25
%S A344129 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 A344129 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 A344129 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 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.
%e A344129 The board is numbered with the square spiral:
%e A344129 .
%e A344129   17--16--15--14--13   .
%e A344129    |               |   .
%e A344129   18   5---4---3  12  29
%e A344129    |   |       |   |   |
%e A344129   19   6   1---2  11  28
%e A344129    |   |           |   |
%e A344129   20   7---8---9--10  27
%e A344129    |                   |
%e A344129   21--22--23--24--25--26
%e A344129 .
%e A344129 a(1) = 0 as the knight starts at the central square numbered 1.
%e A344129 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 A344129 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 A344129 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 A344129 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 A344129 (Python) # uses get_coordinate(n) in A296030
%o A344129 KM=[(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
%o A344129 def next_moves(i, j): return [(i+k, j+m) for k, m in KM]
%o A344129 def a(n):
%o A344129     start, goal, steps = (0, 0), get_coordinate(n), 0
%o A344129     reach, expand = {start}, {start}
%o A344129     while goal not in reach:
%o A344129         reach1 = set(m for i, j in expand for m in next_moves(i, j))
%o A344129         expand = reach1 - reach
%o A344129         steps, reach, reach1 = steps + 1, reach | reach1, set()
%o A344129     return steps
%o A344129 print([a(n) for n in range(1, 101)]) # _Michael S. Branicky_, Jun 15 2021
%Y A344129 Cf. A296030, A174344, A274923, A344046, A316667.
%K A344129 nonn
%O A344129 1,2
%A A344129 _Scott R. Shannon_, May 10 2021