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”).

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

%I #55 Nov 06 2019 03:39:23

%S 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,

%T 18,15,32,29,52,25,46,21,42,69,20,39,16,33,12,27,24,45,74,41,68,103,

%U 36,61,94,57,54,85,50,47,76,113,72,107,150,67,102,63,66,35

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

%C 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.

%C Sequence ends if knight is unable to move.

%C Inspired by A316588 and, like that sequence, has only finitely many terms; see A316667 for details.

%C 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

%C 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

%H Daniël Karssen, <a href="/A316328/b316328.txt">Table of n, a(n) for n = 0..2015</a>

%H M. F. Hasler, <a href="/wiki/Knight_tours">Knight tours</a>, OEIS wiki, Nov. 2019.

%H N. J. A. Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=RGQe8waGJ4w">The Trapped Knight</a>, Numberphile video (2019).

%F a(n) = A316667(n+1) - 1.

%e The board is spirally numbered, starting with 0 at (0,0), as follows:

%e .

%e 16--15--14--13--12 :

%e | | :

%e 17 4---3---2 11 28

%e | | | | |

%e 18 5 0---1 10 27

%e | | | |

%e 19 6---7---8---9 26

%e | |

%e 20--21--22--23--24--25

%e .

%e 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).

%e 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).

%e 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.

%o (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];}

%Y Cf. A316667 (same with offset 1 and values +1), A316338 (numbers not in this sequence).

%Y Cf. A323809 (infinite extension of this sequence).

%Y Cf. A316588 (variant with diagonally numbered board, coordinates x, y >= 0).

%Y 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).

%Y Cf. A326916 and A326918, A326413, A328698 (squares are filled with digits of the infinite word 0,1,...9,1,0,1,1,...).

%Y Cf. A174344, A274923, A296030 (coordinates of a given square).

%K nonn,fini,full,look

%O 0,2

%A _N. J. A. Sloane_, Jul 13 2018

%E Terms from a(17) on computed by _Daniël Karssen_, Jul 10 2018

%E Examples added and crossrefs edited by _M. F. Hasler_, Nov 04 2019