

A316328


Lexicographically earliest knight's path on spiral on infinite chessboard.


25



0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 42, 69, 20, 39, 16, 33, 12, 27, 24, 45, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 50, 47, 76, 113, 72, 107, 150, 67, 102, 63, 66, 35
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

On a doublyinfinite chessboard, number all the cells in a counterclockwise spiral starting at a central cell labeled 0. Start with a knight at cell 0, and thereafter always move the knight to the smallest unvisited cell. Sequence gives succession of squares visited.
Sequence ends if knight is unable to move.
Inspired by A316588 and, like that sequence, has only finitely many terms; see A316667 for details.
See A326924 for a variant where the knight prefers squares closest to the origin, and gets trapped only after 22325 moves.  M. F. Hasler, Oct 21 2019
See A323809 for an infinite extension of this sequence, obtained by allowing the knight to go back in case it was trapped. See A328908 for a variant of length > 10^6, using the taxicab distance, and A328909 for a variant using the sup norm.  M. F. Hasler, Nov 04 2019


LINKS

Daniël Karssen, Table of n, a(n) for n = 0..2015
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).


FORMULA

a(n) = A316667(n+1)  1.


EXAMPLE

The board is spirally numbered, starting with 0 at (0,0), as follows:
.
1615141312 :
  :
17 432 11 28
    
18 5 01 10 27
   
19 6789 26
 
202122232425
.
Coordinates of a point are given in A174344, A274923 and A296030 (but these have offset 1: they list coordinates of the nth point on the spiral, so the coordinates of first point, 0 at the origin, have index n = 1, etc).
Starting at the origin, a(0) = 0, the knight jumps to the square with the lowest number at the eight available positions, (+2, +1) or (+1, +2), which is a(1) = 9 at (2, 1).
From there, the available square with the lowest number is a(2) = 2 at (1, 1): square 0 at the origin is not available since already occupied earlier. Similarly, the knight will not be allowed to go on squares a(1) = 9 or a(2) = 2 ever after.


PROG

(PARI) {local( K=[[(1)^(i\2)<<(i>4), (1)^i<<(i<5)]i<[1..8]], nxt(p, x=coords(p))=vecsort(apply(K>t(x+K), K))[1], pos(x, y)=if(y>=abs(x), 4*y^2yx, x>=abs(y), 4*x^2xy, y>=abs(x), (4*y3)*y+x, (4*x3)*x+y), coords(n, m=sqrtint(n), k=m\/2)=if(m<=n=4*k^2, [n3*k, k], n>=0, [k, kn], n>=m, [kn, k], [k, 3*k+n]), U=[], t(x, p=pos(x[1], x[2]))=if(p<=U[1]setsearch(U, p), oo, p)); my(A=List(0)); for(n=1, oo, U=setunion(U, [A[n]]); while(#U>1&&U[2]==U[1]+1, U=U[^1]); iferr(listput(A, nxt(A[n])), E, break)); print("Index of the last term: ", #A1); A316328(n)=A[n+1]; }


CROSSREFS

Cf. A316667 (same with offset 1 and values +1), A316338 (numbers not in this sequence).
Cf. A323809 (infinite extension of this sequence).
Cf. A316588 (variant with diagonally numbered board, coordinates x, y >= 0).
Cf. A326924 and A326922 (variant: choose square closest to the origin), A328908 and A328928 (variant using taxicab distance); A328909 and A328929 (variant using sup norm).
Cf. A326916 and A326918, A326413, A328698 (squares are filled with digits of the infinite word 0,1,...9,1,0,1,1,...).
Cf. A174344, A274923, A296030 (coordinates of a given square).
Sequence in context: A154838 A082831 A085551 * A323809 A328909 A326924
Adjacent sequences: A316325 A316326 A316327 * A316329 A316330 A316331


KEYWORD

nonn,fini,full,look


AUTHOR

N. J. A. Sloane, Jul 13 2018


EXTENSIONS

Terms from a(17) on computed by Daniël Karssen, Jul 10 2018
Examples added and crossrefs edited by M. F. Hasler, Nov 04 2019


STATUS

approved



