login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A316328
Lexicographically earliest knight's path on spiral on infinite chessboard.
29
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
OFFSET
0,2
COMMENTS
On a doubly-infinite 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
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:
.
16--15--14--13--12 :
| | :
17 4---3---2 11 28
| | | | |
18 5 0---1 10 27
| | | |
19 6---7---8---9 26
| |
20--21--22--23--24--25
.
Coordinates of a point are given in A174344, A274923 and A296030 (but these have offset 1: they list coordinates of the n-th 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^2-y-x, -x>=abs(y), 4*x^2-x-y, -y>=abs(x), (4*y-3)*y+x, (4*x-3)*x+y), coords(n, m=sqrtint(n), k=m\/2)=if(m<=n-=4*k^2, [n-3*k, -k], n>=0, [-k, k-n], n>=-m, [-k-n, 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: ", #A-1); 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: A378388 A082831 A085551 * A323809 A328909 A326924
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