login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328908 Knight tour on spirally numbered infinite chessboard, when the knight always jumps on the unvisited square closest to the origin, first according to 1-norm, then 2-norm, then number of the square: a(n) = number of the square visited at the n-th 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 2-norm 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 1-norm 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 1-norm (or taxicab distance) of the square visited at the n-th 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 co-ordinates (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 1-norm (= 7) over A326924(73) = 81 with coordinates (5, -4), having 1-norm 5 + 4 = 9 but Euclidean or 2-norm 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^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]), t(x, p=pos(x[1], x[2]))=if(p<Umin||bittest(U, p-Umin), 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: ", #A-1); A328908(n)=A[n+1]; }

CROSSREFS

Cf. A328928 for the "value" (= 1-norm) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 7 06:47 EST 2021. Contains 341868 sequences. (Running on oeis4.)