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