A383185 Number of the square visited by a king moving on a spirally numbered board always to the lowest available unvisited square, when a wall delimiting the spiral must be crossed on each move.

0, 3, 13, 2, 10, 1, 7, 21, 6, 18, 4, 14, 32, 12, 28, 11, 27, 9, 23, 8, 22, 44, 20, 40, 19, 5, 17, 37, 16, 34, 15, 33, 59, 31, 57, 30, 54, 29, 53, 85, 51, 25, 47, 24, 46, 76, 45, 75, 43, 73, 42, 70, 41, 69, 39, 67, 38, 66, 36, 62, 35, 61, 95, 60, 94, 58, 92, 56, 88, 55, 87, 127, 86, 52, 26

Offset: 0

Author

M. F. Hasler, May 12 2025

Keywords

• nonn
• walk

Comments

The board is numbered following a square spiral starting with 0 at the origin (where the king is at n = 0) and delimited by a wall that must be crossed on each move:

.

16 15 14 13 12 | .

,-----------. | .

17 | 4 3 2 |11 | .

| ,--- | | .

18 | 5 | 0 1 |10 | .

| '-------' | .

19 | 6 7 8 9 | .

`---------------' .

20 21 22 23 24 25

.

A line drawn from the center of the starting square to the center of the ending square must pass through a wall on each move. A move that would just touch a wall without passing through the wall (e.g., 0 to 2) is not permissible. Equivalently, the king can't move from a square labeled k to a square labeled k +- 1 or k +- 2, i.e., |a(n)-a(n+1)| > 2 for all n.

This sequence is a permutation of the nonnegative integers, see A383186 for the inverse permutation. The king's walk indeed fills the 2D grid with an initial segment S0 of 24 moves, followed by rings R(r), r >= 1, which consist of three shells S1(r), S2(r) and S3(r), each of which corresponds to a tour around the center. Each ring R(r) starts with the move number n = 48 r^2 - 16 r + 1 = (25, 147, 365, ...) to the square at position P(r) = (2-3r, 3r-3) = ((-1,0), (-4,3), (-7,6), ...), and contains a perfectly well defined sequence of 96 r + 26 grid points following a precise sequence of pattern given in full detail on the wiki page provided in the links section.

Examples

			For n = 1, a(1) = 3 because moving from 0 to 1 or 2 does not pass through a wall.
		

Links

• M. F. Hasler, Table of n, a(n) for n = 0..1000
• M. F. Hasler, A383185: Details about the grid filling king's walk, OEIS wiki, May 15, 2025.
• M. F. Hasler, Path plot with annotations, May 15, 2025.
• OEIS index to sequences related to permutations of the integers.

Crossrefs

Cf. A375925 (the same with indices and numbers of squares starting at 1).

Cf. A383186 (inverse permutation).

Cf. A316328 (knight's path), A033638, A316667 (trapped knight), A336038 (trapped king), A335856 (trapped king preferably moving to prime numbers).

Programs

Python

def square_number(z): return int(4*y**2-y-x if (y := z.imag) >= abs(x := z.real)
    else 4*x**2-x-y if -x>=abs(y) else (4*y-3)*y+x if -y>=abs(x) else (4*x-3)*x+y)
def A383185(n):
    if not hasattr(A:=A383185, 'terms'): A.terms=[0]; A.pos=0; A.path=[0]
    while len(A.terms) <= n:
        s,d = min((s,d) for d in (1, 1+1j, 1j, 1j-1, -1, -1-1j, -1j, 1-1j) if
            abs((s:=square_number(A.pos+d))-A.terms[-1]) > 2 and s not in A.terms)
        A.terms.append(s); A.pos += d; A.path.append(A.pos)
    return A.terms[n]
import matplotlib.pyplot as plt # this and below to plot the trajectory
plt.plot([z.real for z in A383185.path], [z.imag for z in A383185.path])
plt.show()