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!)
A316328 Lexicographically earliest knight's path on spiral on infinite chessboard. 25
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, 42, 69, 20, 39, 16, 33, 12, 27, 24, 45, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 50, 47, 76, 113, 72, 107, 150, 67, 102, 63, 66, 35 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

On a doubly-infinite chessboard, number all the cells in a counterclockwise spiral starting at a central cell labeled 0. Start with a knight at cell 0, and thereafter always move the knight to the smallest unvisited cell. Sequence gives succession of squares visited.

Sequence ends if knight is unable to move.

Inspired by A316588 and, like that sequence, has only finitely many terms; see A316667 for details.

See A326924 for a variant where the knight prefers squares closest to the origin, and gets trapped only after 22325 moves. - M. F. Hasler, Oct 21 2019

See A323809 for an infinite extension of this sequence, obtained by allowing the knight to go back in case it was trapped. See A328908 for a variant of length > 10^6, using the taxicab distance, and A328909 for a variant using the sup norm. - M. F. Hasler, Nov 04 2019

LINKS

Daniël Karssen, Table of n, a(n) for n = 0..2015

M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.

N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

FORMULA

a(n) = A316667(n+1) - 1.

EXAMPLE

The board is spirally numbered, starting with 0 at (0,0), as follows:

.

  16--15--14--13--12   :

   |               |   :

  17   4---3---2  11  28

   |   |       |   |   |

  18   5   0---1  10  27

   |   |           |   |

  19   6---7---8---9  26

   |                   |

  20--21--22--23--24--25

.

Coordinates of a point are given in A174344, A274923 and A296030 (but these have offset 1: they list coordinates of the n-th point on the spiral, so the coordinates of first point, 0 at the origin, have index n = 1, etc).

Starting at the origin, a(0) = 0, the knight jumps to the square with the lowest number at the eight available positions, (+-2, +-1) or (+-1, +-2), which is a(1) = 9 at (2, -1).

From there, the available square with the lowest number is a(2) = 2 at (1, 1): square 0 at the origin is not available since already occupied earlier. Similarly, the knight will not be allowed to go on squares a(1) = 9 or a(2) = 2 ever after.

PROG

(PARI) {local( K=[[(-1)^(i\2)<<(i>4), (-1)^i<<(i<5)]|i<-[1..8]], nxt(p, x=coords(p))=vecsort(apply(K->t(x+K), K))[1], 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=[], t(x, p=pos(x[1], x[2]))=if(p<=U[1]||setsearch(U, p), oo, p)); my(A=List(0)); 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 the last term: ", #A-1); A316328(n)=A[n+1]; }

CROSSREFS

Cf. A316667 (same with offset 1 and values +1), A316338 (numbers not in this sequence).

Cf. A323809 (infinite extension of this sequence).

Cf. A316588 (variant with diagonally numbered board, coordinates x, y >= 0).

Cf. A326924 and A326922 (variant: choose square closest to the origin), A328908 and A328928 (variant using taxicab distance); A328909 and A328929 (variant using sup norm).

Cf. A326916 and A326918, A326413, A328698 (squares are filled with digits of the infinite word 0,1,...9,1,0,1,1,...).

Cf. A174344, A274923, A296030 (coordinates of a given square).

Sequence in context: A154838 A082831 A085551 * A323809 A328909 A326924

Adjacent sequences:  A316325 A316326 A316327 * A316329 A316330 A316331

KEYWORD

nonn,fini,full,look

AUTHOR

N. J. A. Sloane, Jul 13 2018

EXTENSIONS

Terms from a(17) on computed by Daniël Karssen, Jul 10 2018

Examples added and crossrefs edited by M. F. Hasler, Nov 04 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 July 10 05:09 EDT 2020. Contains 335572 sequences. (Running on oeis4.)