A326924 Squares visited by a knight on a spirally numbered board, moving always to the unvisited square closest to the origin.

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, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 81

Offset: 0

Author

M. F. Hasler, Oct 21 2019

Keywords

• nonn
• fini
• full

Comments

"Closest to the origin" is meant in the sense of Euclidean distance, and in case of a tie, the square coming earliest on the spiral.

Differs from the original A316328 from a(34) = 76 on. See there for more information and other related sequences.

The knight gets trapped at the 22325th move at position (x,y) = (81, -18), from which it can't reach any unvisited square.

Sequence A326922 gives the distance^2 of the square number a(n) visited at move n. - M. F. Hasler, Oct 22 2019

From M. F. Hasler, Nov 04 2019: (Start)

When a(22325) = 25983 at (81, -18) is reached, at distance sqrt(6885) from the origin, the last unvisited square has number 13924, at (-59, 59), distance sqrt(6962) from the origin. This suggests that in an infinite extension (knight moves one step back if no unvisited square is available, cf. A323809) the knight might eventually visit every square. Can this be disproved by a counterexample of a square which will never be visited in the infinite extension? (In A328908 such a counterexample exists even before the knight gets stuck.)

The ratio a(n)/n oscillates between 0.5 and less than 1.7 for all n > 3000, even < 1.5 for all n > 14000, cf. graph of the sequence. What is the superior and inferior limit of this ratio, assuming the infinite extension beyond n = 22325?

(End)

Links

• M. F. Hasler, Table of n, a(n) for n = 0..22325
• M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
• M. F. Hasler, Plot of knight tour A326924(0..22325), ending at (x,y) = (81,-18), Oct 20 2022.

Crossrefs

Cf. A316328, A326918, A326922.

Cf. A326413, A326916, A316667; A328908, A328928; A328909, A328929; A326413, A328698.

Cf. A174344, A274923, A296030 (coordinate of square number n).

Programs

PARI

{local(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=[]/* used squares */, K=vector(8, i, [(-1)^(i\2)<<(i>4), (-1)^i<<(i<5)])/* knight moves */, 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), t(x, p=pos(x[1],x[2]))=if(p<=U[1]||setsearch(U, p), oo, [norml2(x),p]), nxt(p, x=coords(p))=vecsort(apply(K->t(x+K), K))[1][2]); my(A=List(0)/*list of positions*/); 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 last term: ", #A-1); A326924(n)=A[n+1];} \\ To compute the infinite extension, set upper bound in for() loop and replace "break" by listput(A, A[n-1])