

A328908


Knight tour on spirally numbered infinite chessboard, when the knight always jumps on the unvisited square closest to the origin, first according to 1norm, then 2norm, then number of the square: a(n) = number of the square visited at the nth move.


12



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, 175
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Differs from A326924 (where only the 2norm is considered) from a(73) = 175 on.
The sequence is also finite, when the knight lands on square number a(1092366) there is no unvisited square within reach.
The 1norm or taxicab distance from the origin of the square a(n) is given in A328928(n).
It appears that this knight tour would also completely fills the board, if we consider the infinite extension where the knight is allowed to move back on its last step(s) when there's no unvisited square available: no isolated sets of unvisited squares as defined in A323809, seem to occur. Is there a proof or disproof for this?  M. F. Hasler, Nov 04 2019


LINKS

M. F. Hasler, Table of n, a(n) for n = 0..100000
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.


FORMULA

A328928(n) = A174344(a(n)) + A274923(a(n)), the 1norm (or taxicab distance) of the square visited at the nth step.


EXAMPLE

The squares are numbered as in the spiral given in A174344 (upside down to get a counterclockwise spiral, but this is irrelevant here).
The knight starts at a(0) = 0 with coordinates (0, 0).
It jumps to a(1) = 9 with coordinates (2, 1): all 8 available squares (+2, +1) and (+1, +2) are at the same taxicab (2 + 1 = 3) and Euclidean distance (sqrt(2^2 + 1^2) = sqrt(5)) from the origin, but square number 9 has the smallest number.
a(73) = 175 with coordinates (7, 0) is the first destination which is preferred due to the 1norm (= 7) over A326924(73) = 81 with coordinates (5, 4), having 1norm 5 + 4 = 9 but Euclidean or 2norm sqrt(41) smaller than 7.
a(1000) = 816 with coordinates (10, 14).
a(2000) = 2568 with coordinates (7, 25).
a(5000) = 4476 with coordinates (21, 33).
a(10000) = 15560 with coordinates (2, 62).
a(20000) = 19566 with coordinates (36, 70).
a(50000) = 62092 with coordinates (125, 33).
a(10^5) = 135634 with coordinates (184, 26), taxicab distance 210 from the origin.
a(200'000) = 259798 with coordinates (47, 255).
a(500'000) = 713534 with coordinates (68, 422).
a(1'000'000) = 995288 with coordinates (217, 499).
a(1'092'366) = 1165672 with coordinates (188, 540), taxicab norm 728 from the origin, is the last square visited by the knight before there is no unvisited square within reach.
By then the earliest square on the spiral not yet visited is number 629641 at (397, 396), taxicab norm 793, and the unvisited square closest to the origin is number 1794929 at (1, 670), taxicab norm 671.


PROG

(PARI) {Nmax=1e5; /* Full seq. with > 10^6 terms takes long 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^2yx, x>=abs(y), 4*x^2xy, y>=abs(x), (4*y3)*y+x, (4*x3)*x+y), coords(n, m=sqrtint(n), k=m\/2)=if(m<=n=4*k^2, [n3*k, k], n>=0, [k, kn], n>=m, [kn, k], [k, 3*k+n]), t(x, p=pos(x[1], x[2]))=if(p<Uminbittest(U, pUmin), oo, [normlp(x, 1), norml2(x), p]), nxt(p, x=coords(p))=vecsort(apply(K>t(x+K), K))[1][3], U=0, Umin=0); my(A=List(0)); for(n=1, Nmax, U+=1<<(A[n]Umin); while(bittest(U, 0), U>>=1; Umin++); iferr(listput(A, nxt(A[n])), E, break)); print("Index of the last term: ", #A1); A328908(n)=A[n+1]; }


CROSSREFS

Cf. A328928 for the "value" (= 1norm) on the visited square.
Cf. A316328 ~ A316667, A326924, A328909 (variants).
Cf. A174344, A274923, A296030 (coordinates of square number n).
Sequence in context: A323809 A328909 A326924 * A275967 A155799 A021112
Adjacent sequences: A328905 A328906 A328907 * A328909 A328910 A328911


KEYWORD

nonn,fini,walk,changed


AUTHOR

M. F. Hasler, Oct 31 2019


STATUS

approved



