cp's OEIS Frontend

A323809 Squares visited by a knight on a spirally numbered board, moving always to the lowest available unvisited square, or one step back if no unvisited square is available.

%I A323809 #34 Aug 17 2025 01:42:06
%S A323809 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 A323809 18,15,32,29,52,25,46,21,42,69,20,39,16,33,12,27,24,45,74,41,68,103,
%U A323809 36,61,94,57,54,85,50,47,76,113,72,107,150,67,102,63,66,35,38,65,62
%N A323809 Squares visited by a knight on a spirally numbered board, moving always to the lowest available unvisited square, or one step back if no unvisited square is available.
%C A323809 This is an infinite extension of A316328, with which it coincides for the first 2016 terms. - _N. J. A. Sloane_, Jan 29 2019
%C A323809 From _M. F. Hasler_, Nov 04 2019: (Start)
%C A323809 At move 99999, the least yet unvisited square has number 66048, which is near the border of the visited region. This suggests that the knight will eventually visit every square. Can this be proved or disproved through a counterexample?
%C A323809 More formally, let us call "isolated" a set of unvisited squares which is connected through knight moves, but which cannot be extended to a larger such set by adding a further square. Can there exist at some moment a finite isolated set which the knight cannot reach? (Without the last condition, the square a(2016) would clearly satisfy the condition just before the knight reaches it.)
%C A323809 Such subsets have a good chance of preserving this property forever. It should be possible to prove that an isolated subset sufficiently far (2 knight moves?) from any other unvisited square (or from the infinite connected subset of unvisited squares) remains so forever. (This condition of distance could replace the time-dependent condition "reachable by the knight".)
%C A323809 If such (forever) isolated sets do exist, with what frequency will they occur? Could they have a nonzero asymptotic density? Will this (if so, how) depend on the way the knight measures "lowest available" (cf. variants where the taxicab or Euclidean or sup norm distance from the origin is used)? (End)
%H A323809 Daniël Karssen, <a href="/A323809/b323809.txt">Table of n, a(n) for n = 0..99999</a>
%H A323809 M. F. Hasler, <a href="/wiki/Knight_tours">Knight tours</a>, OEIS wiki, Nov. 2019.
%H A323809 Daniël Karssen, <a href="/A323809/a323809.svg">Figure showing the first 1e5 steps of the sequence</a>
%F A323809 a(n) = A323808(n+1) - 1. - _M. F. Hasler_, Nov 06 2019
%e A323809 The board is numbered following a square spiral:
%e A323809   16--15--14--13--12   :
%e A323809    |               |   :
%e A323809   17   4---3---2  11  28
%e A323809    |   |       |   |   |
%e A323809   18   5   0---1  10  27
%e A323809    |   |           |   |
%e A323809   19   6---7---8---9  26
%e A323809    |                   |
%e A323809   20--21--22--23--24--25
%e A323809 .
%e A323809 From _M. F. Hasler_, Nov 06 2019: (Start)
%e A323809 At move 2015, the knight lands on a(2015) = 2083, from where no unvisited squares can be reached. So the knight moves back to a(2016) = a(2014) = 2466, from where it goes on to the unvisited square a(2017) = 2667.
%e A323809 Similarly, at moves 2985, 3120, 3378, 7493, 8785, 9738, 10985, 11861, 11936, 12160, 18499, 18730, 19947 and 22251, the knight get "trapped" and has to move to the previous square on the next move.
%e A323809 On move 23044, the same happens on square 25808, and the knight must move back to square a(23045) = a(23043) = 27111. However, there is still no unvisited square in reach, so the knight has to make another step back to a(23046) = a(23042) = 28446, before it can move on to a(23047) = 29123. (End)
%o A323809 (PARI) Nmax=1e5 /* number of terms to compute */; {local( K=[[(-1)^(i\2)<<(i>4),(-1)^i<<(i<5)]|i<-[1..8]], 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=0, Umin=0, t(x, p=pos(x[1],x[2]))=if(p<Umin||bittest(U, p-Umin), oo, p), nxt(p, x=coords(p))=vecsort(apply(K->t(x+K), K))[1], back=0); my(A=List(0)); for(n=1, Nmax, back||U+=1<<(A[n]-Umin); while(bittest(U,0), U>>=1; Umin++); listput(A, nxt(A[n])); if(A[n+1] != oo, back=0, A[n+1]=A[n+1-back+=2])); print("Index of the last term: ", #A-1); A323809(n)=A[n+1];}
%Y A323809 The sequences involved in this set of related sequences are A316588, A316328, A316334, A316667, A323808, A323809, A323810 and A323811.
%Y A323809 Cf. A326924 & A326922 (using L2-norm), A328908 & A328928 (L1-norm), A328909 & A328929 (sup norm); A326916 & A326918 (digits on spiral), A326413 and A328698 (variants with other tie breaker).
%K A323809 nonn,walk
%O A323809 0,2
%A A323809 _Daniël Karssen_, Jan 28 2019
%E A323809 Edited by _M. F. Hasler_, Nov 02 2019