|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
|
|
|
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).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Examples added and crossrefs edited by M. F. Hasler, Nov 04 2019
|
|
|
STATUS
|
approved
|
| |
|
|
