|
%I #49 Feb 01 2022 00:30:27
%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,76,47,50,27,12,33,16,39,20,45,24,51,48,77,
%U 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
%N Knight's 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.
%C Differs from A326924 (where only the 2-norm is considered) from a(73) = 175 on.
%C The sequence is also finite, when the knight lands on square number a(1092366) there is no unvisited square within reach.
%C The 1-norm or taxicab distance from the origin of the square a(n) is given in A328928(n).
%C It appears that this knight's 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
%H M. F. Hasler, <a href="/A328908/b328908.txt">Table of n, a(n) for n = 0..100000</a>
%H M. F. Hasler, <a href="/wiki/Knight_tours">Knight tours</a>, OEIS wiki, Nov. 2019.
%F A328928(n) = |A174344(a(n))| + |A274923(a(n))|, the 1-norm (or taxicab distance) of the square visited at the n-th step.
%e The squares are numbered as in the spiral given in A174344 (upside down to get a counterclockwise spiral, but this is irrelevant here).
%e The knight starts at a(0) = 0 with coordinates (0, 0).
%e 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.
%e 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.
%e a(1000) = 816 with coordinates (-10, -14).
%e a(2000) = 2568 with coordinates (-7, -25).
%e a(5000) = 4476 with coordinates (21, -33).
%e a(10000) = 15560 with coordinates (-2, -62).
%e a(20000) = 19566 with coordinates (-36, 70).
%e a(50000) = 62092 with coordinates (125, -33).
%e a(10^5) = 135634 with coordinates (-184, -26), taxicab distance 210 from the origin.
%e a(200'000) = 259798 with coordinates (47, 255).
%e a(500'000) = 713534 with coordinates (-68, -422).
%e a(1'000'000) = 995288 with coordinates (217, 499).
%e 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.
%e 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.
%o (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];}
%Y Cf. A328928 for the "value" (= 1-norm) on the visited square.
%Y Cf. A316328 ~ A316667, A326924, A328909 (variants).
%Y Cf. A174344, A274923, A296030 (coordinates of square number n).
%K nonn,fini,walk
%O 0,2
%A _M. F. Hasler_, Oct 31 2019
|
