A323808 -id:A323808 - cp's OEIS frontend

A316667 Squares visited by a knight moving on a spirally numbered board always to the lowest available unvisited square.

1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 29, 32, 15, 12, 27, 24, 45, 20, 23, 44, 41, 18, 35, 38, 19, 16, 33, 30, 53, 26, 47, 22, 43, 70, 21, 40, 17, 34, 13, 28, 25, 46, 75, 42, 69, 104, 37, 62, 95, 58, 55, 86, 51, 48, 77, 114, 73, 108, 151, 68, 103, 64, 67, 36

Offset: 1

Daniël Karssen, Jul 10 2018, following a suggestion from N. J. A. Sloane, Jul 09 2018

Board is numbered with the square spiral:
.
  17--16--15--14--13   .
   |               |   .
  18   5---4---3  12   .
   |   |       |   |   .
  19   6   1---2  11   .
   |   |           |   .
  20   7---8---9--10   .
   |                   .
  21--22--23--24--25--26
.
This sequence is finite: At step 2016, square 2084 is visited, after which there are no unvisited squares within one knight move.

Daniël Karssen, Table of n, a(n) for n = 1..2016
Daniël Karssen, Figure showing the first 60 steps of the sequence
Daniël Karssen, Figure showing the complete sequence
Daniël Karssen, MATLAB script to generate the complete sequence
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

Cf. A316328 (same starting at 0), A329022 (same with diamond-shaped spiral), A316588 (variant on board with x,y >= 0).
Cf. A326924 (choose square closest to the origin), A328908 (using taxicab distance), A328909 (using sup norm); A323808, A323809.
The (x,y) coordinates of square k are (A174344(k), A274923(k)).

A316667(n)=A316328(n-1)+1 \\ M. F. Hasler, Nov 06 2019

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

A323809 Squares visited by a knight on a spirally numbered board, moving always to the lowest available unvisited square, or one step back if no unvisited square is available.

Original entry on oeis.org

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, 38, 65, 62

Offset: 0

Daniël Karssen, Jan 28 2019

This is an infinite extension of A316328, with which it coincides for the first 2016 terms. - N. J. A. Sloane, Jan 29 2019
From M. F. Hasler, Nov 04 2019: (Start)
At move 99999, the least yet unvisited square has number 66048, which is near the border of the visited region. This suggests that the knight will eventually visit every square. Can this be proved or disproved through a counterexample?
More formally, let us call "isolated" a set of unvisited squares which is connected through knight moves, but which cannot be extended to a larger such set by adding a further square. Can there exist at some moment a finite isolated set which the knight cannot reach? (Without the last condition, the square a(2016) would clearly satisfy the condition just before the knight reaches it.)
Such subsets have a good chance of preserving this property forever. It should be possible to prove that an isolated subset sufficiently far (2 knight moves?) from any other unvisited square (or from the infinite connected subset of unvisited squares) remains so forever. (This condition of distance could replace the time-dependent condition "reachable by the knight".)
If such (forever) isolated sets do exist, with what frequency will they occur? Could they have a nonzero asymptotic density? Will this (if so, how) depend on the way the knight measures "lowest available" (cf. variants where the taxicab or Euclidean or sup norm distance from the origin is used)? (End)

			The board is numbered following a square spiral:
  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
.
From _M. F. Hasler_, Nov 06 2019: (Start)
At move 2015, the knight lands on a(2015) = 2083, from where no unvisited squares can be reached. So the knight moves back to a(2016) = a(2014) = 2466, from where it goes on to the unvisited square a(2017) = 2667.
Similarly, at moves 2985, 3120, 3378, 7493, 8785, 9738, 10985, 11861, 11936, 12160, 18499, 18730, 19947 and 22251, the knight get "trapped" and has to move to the previous square on the next move.
On move 23044, the same happens on square 25808, and the knight must move back to square a(23045) = a(23043) = 27111. However, there is still no unvisited square in reach, so the knight has to make another step back to a(23046) = a(23042) = 28446, before it can move on to a(23047) = 29123. (End)

Daniël Karssen, Table of n, a(n) for n = 0..99999
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
Daniël Karssen, Figure showing the first 1e5 steps of the sequence

The sequences involved in this set of related sequences are A316588, A316328, A316334, A316667, A323808, A323809, A323810 and A323811.

Cf. A326924 & A326922 (using L2-norm), A328908 & A328928 (L1-norm), A328909 & A328929 (sup norm); A326916 & A326918 (digits on spiral), A326413 and A328698 (variants with other tie breaker).

Nmax=1e5 /* number of terms 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]), U=0, Umin=0, t(x, p=pos(x[1],x[2]))=if(pt(x+K), K))[1], back=0); my(A=List(0)); for(n=1, Nmax, back||U+=1<<(A[n]-Umin); while(bittest(U,0), U>>=1; Umin++); listput(A, nxt(A[n])); if(A[n+1] != oo, back=0, A[n+1]=A[n+1-back+=2])); print("Index of the last term: ", #A-1); A323809(n)=A[n+1];}

a(n) = A323808(n+1) - 1. - M. F. Hasler, Nov 06 2019

Edited by M. F. Hasler, Nov 02 2019

A323714 Squares where knight moving to a lowest unvisited square on a spirally numbered board will have no available moves.

Original entry on oeis.org

2084, 2720, 3325, 3753, 7776, 5632, 7411, 8562, 14076, 8469, 9231, 22702, 14661, 21710, 21078, 25809, 27112, 24708, 19844, 26943, 26737, 32449, 31366, 45036, 37853, 37188, 43318, 62095, 67401, 68736

Offset: 1

Sami Mäki, Jan 25 2019

First term is the last term of A316667. Next terms are given by repeatedly blocking the squares where the knight would not have any available moves.
Plotting the terms on XY-plane seems to show a clear pattern where most of the points only land on certain directions from the center.
Inspired by A316667 and comments on N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Sami Mäki, Table of n, a(n) for n = 1..4000
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Cf. A316667, A323808.

A323810 Squares visited by a knight on a diagonally numbered board and moving to the lowest available unvisited square at each step and if no unvisited squares are available move one step back.

Original entry on oeis.org

1, 8, 6, 2, 12, 9, 4, 3, 13, 7, 5, 10, 26, 18, 11, 30, 24, 16, 38, 31, 22, 17, 25, 20, 28, 34, 14, 21, 43, 33, 27, 19, 15, 35, 42, 32, 23, 29, 39, 47, 56, 69, 37, 48, 40, 51, 60, 70, 57, 67, 81, 46, 58, 49, 41, 52, 44, 55, 64, 36, 65, 53, 45, 76, 63, 54, 66, 103, 88, 74, 61

Offset: 1

Daniël Karssen, Jan 28 2019

nonn

Board is numbered as follows:
   1  2  4  7 11 16  .
   3  5  8 12 17  .
   6  9 13 18  .
  10 14 19  .
  15 20  .
  21  .
  .
Coincides with A316588 for the first 2402 terms. - Daniël Karssen, Jan 30 2019

Daniël Karssen, Table of n, a(n) for n = 1..100000
Daniël Karssen, Figure showing the first 1e5 steps of the sequence

The sequences involved in this set of related sequences are A316588, A316328, A316334, A316667, A323808, A323809, A323810, and A323811.

A323811 Squares visited by a knight on a diagonally numbered board and moving to the lowest available unvisited square at each step and if no unvisited squares are available move one step back.

Original entry on oeis.org

0, 7, 5, 1, 11, 8, 3, 2, 12, 6, 4, 9, 25, 17, 10, 29, 23, 15, 37, 30, 21, 16, 24, 19, 27, 33, 13, 20, 42, 32, 26, 18, 14, 34, 41, 31, 22, 28, 38, 46, 55, 68, 36, 47, 39, 50, 59, 69, 56, 66, 80, 45, 57, 48, 40, 51, 43, 54, 63, 35, 64, 52, 44, 75, 62, 53, 65, 102, 87, 73, 60

Offset: 0

Daniël Karssen, Jan 28 2019

nonn

Board is numbered as follows:
   0  1  3  6 12 17  .
   2  4  7 13 18  .
   5 10 14 19  .
  11 15 20  .
  16 21  .
  22  .
  .
Coincides with A316334 for the first 2402 terms.

Daniël Karssen, Table of n, a(n) for n = 0..99999
Daniël Karssen, Figure showing the first 1e5 steps of the sequence

The sequences involved in this set of related sequences are A316588, A316328, A316334, A316667, A323808, A323809, A323810, and A323811.

A343356 Squares visited by a knight moving on a square-spiral with numbers equal to the ordered prime factors of the positive integers and where the knight moves to the smallest numbered unvisited square; the minimum distance from the origin is used if the square numbers are equal; the smallest ordered spiral number is used if the distances are equal.

Original entry on oeis.org

1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 5, 2, 2

Offset: 1

Scott R. Shannon, Apr 12 2021

Many of the visited squares are numbered 2 due to the large number of such terms on the board and the knight's preference for the lowest available numbered square.
The sequence is finite. After 369 steps the square with spiral number 3, with ordered spiral number 522, is reached after which all eight adjacent squares have been visited. The visited square with the largest spiral number is 41.
See A343385 for the visited squares given as the ordered spiral numbers.

			The square-spiral starts with 1 and is then numbered with the ordered prime factors of the positive integers as follows:
.
  11---5---2---3---3   .
   |               |   .
   2   2---2---3   2   2
   |   |       |   |   |
   2   5   1---2   2   2
   |   |           |   |
   3   2---3---7---2   2
   |                   |
  13---2---7---3---5---2
.
a(1) = 1, the starting square of the knight.
a(2) = 2. Four squares the knight can step to from the starting square are numbered 2, all of which are the same distance form the origin, so the 2 with the lowest spiral number is chosen. This is the 2 at coordinates (2,-1) relative to the starting square which has an ordered spiral number of 10.
a(35) = 3. This is the first time a square greater than 2 is stepped to. The available squares after 33 steps are 3, 3, 3, 11, 5, and 47, and the 3 at coordinates (1,4) relative to the starting square is chosen because it is the closest number to that square.
a(365) = 41. This is the largest numbered square that is stepped to. The available squares after the 363rd step are 41, 157, 313, and 43, and 41 is the smallest of these.
a(370) = 3. This is the final square stepped to as no further unvisited square is available.

N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).
Scott R. Shannon, Image showing the 370 visited squares. The starting square is highlighted in white, the visited squares in yellow, the path is colored across the spectrum to show the relative step ordering, and the final square is highlighted in red.

Cf. A343385, A343388, A316667, A323714, A323808, A329519, A329520, A335844.

A343388 Squares visited by a knight moving on a square-spiral with numbers equal to the ordered divisors of the positive integers and where the knight moves to the smallest numbered unvisited square; the minimum distance from the origin is used if the square numbers are equal; the smallest ordered spiral number is used if the distances are equal.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 4, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 5, 1, 1, 3, 1, 4, 1, 1, 8, 1, 3, 2, 2, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1

Offset: 1

Scott R. Shannon, Apr 13 2021

Many of the visited squares are numbered 1 due to the large number of such terms on the board and the knight's preference for the lowest available numbered square.
The sequence is finite. After 358 steps the square with spiral number 13, with ordered spiral number 37, is reached after which all eight adjacent squares have been visited. The visited square with the largest spiral number is 28.
See A343389 for the visited squares given as the ordered spiral numbers.

			The square-spiral is numbered with the ordered divisors of the positive integers as follows:
.
   1---7---1---6---3   .
   |               |   .
   2   3---1---2   2   11
   |   |       |   |   |
   4   1   1---1   1   1
   |   |           |   |
   8   2---4---1---5   10
   |                   |
   1---3---9---1---2---5
.
a(1) = 1, the starting square of the knight.
a(2) = 1. One square numbered 1 can be stepped to from the starting square, the square with coordinates (1,-2) relative to that square.
a(9) = 2. This is the first time a square greater than 1 is stepped to. The available squares after 7 steps are 3, 11, 10, 2, 9, 2, and 3. The 2 at coordinates (-1,-1) relative to the starting square is because it is the closest number to that square.
a(146) = 28. This is the largest numbered square that is stepped to. The available squares after the 144th step are 117, 213, 47, 70, 61, and 28, and 28 is the smallest of these.
a(359) = 13. This is the final square stepped to as no further unvisited square is available.

Scott R. Shannon, Image showing the 359 visited squares. The starting square is highlighted in white, the visited squares in yellow, the path is colored across the spectrum to show the relative step ordering, and the final square is highlighted in red.

Cf. A343389, A343356, A316667, A323714, A323808, A329519, A329520, A335844.

A336208 Squares visited by a knight on a square-spiral numbered board and moving to the lowest available unvisited square at each step, where the step is not in the same direction as the previous step.

Original entry on oeis.org

1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 29, 32, 15, 12, 27, 24, 49, 52, 25, 28, 13, 34, 17, 40, 21, 46, 75, 22, 19, 16, 33, 30, 53, 26, 47, 80, 51, 48, 23, 44, 41, 18, 37, 62, 99, 36, 39, 20, 43, 70, 109, 42, 45, 74, 71, 110, 113, 72, 111, 154, 73, 108

Offset: 1

Scott R. Shannon, Jul 12 2020

This is a variation of A316667. The same knight move rules apply, but at each step the knight cannot move in the same direction as its previous step.
The sequence is finite. After 217 steps the square with spiral number 118 is reached after which all surrounding squares have been visited.
The first term where this sequence differs from A316667 is a(19) = 49. The previous step was from a(17) = 27 to a(18) = 24, a step 1 unit down and 2 units to the left. The minimum unvisited spiral number one knight leap away from 24 is 45, but that is also in a direction 1 unit down and 2 units to the left, so cannot be chosen. The next closest unvisited square is 49, 1 unit down and 2 units to the right.

			The board is numbered with the square spiral:
.
  17--16--15--14--13   .
   |               |   .
  18   5---4---3  12   29
   |   |       |   |   |
  19   6   1---2  11   28
   |   |           |   |
  20   7---8---9--10   27
   |                   |
  21--22--23--24--25--26
.
a(1) = 1, the starting square of the knight.
a(2) = 10. The eight unvisited squares one knight leap away from a(1) are numbered 10,12,14,16,18,20,22,24. Of these 10 is the lowest.
a(19) = 49. The four unvisited squares one knight leap away from a(18) = 24 are numbered 45,49,77,79. Of these 45 is the lowest but that would require a step 1 unit down and 2 units left from 24, which is the same step as a(17) = 27 to a(18) = 24, so is not allowed. The next lowest available square is 49.

Scott R. Shannon, Table of n, a(n) for n = 1..218
Scott R. Shannon, Image showing the 217 steps of the knight's path. The green dot is the first square with number 1 and the red dot the last square with number 118. The red dot is surrounded by blue dots to show the eight occupied squares. The yellow dots marks the smallest unvisited square with number 145.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Cf. A316667, A336038, A323714, A323808, A329519, A329520.

A343385 The ordered square spiral numbers visited by the knight in A343356.

Original entry on oeis.org

1, 10, 29, 2, 5, 40, 7, 4, 11, 26, 83, 174, 123, 84, 27, 12, 15, 18, 35, 64, 97, 36, 65, 142, 63, 66, 149, 102, 143, 146, 103, 100, 141, 62, 33, 58, 55, 28, 87, 178, 131, 92, 31, 54, 13, 60, 139, 248, 191, 316, 247, 136, 91, 182, 185, 132, 237, 300, 371, 450, 295, 228, 173, 82, 49, 78, 45, 74

Offset: 1

Scott R. Shannon, Apr 13 2021

This is the ordered square-spiral numbers visited by a knight on a square spiral as numbered in A343356. See that sequence for further details.

Scott R. Shannon, Image showing the 370 visited squares. The spiral is numbered with the ordered spiral numbers. The starting square is highlighted in white, the visited squares in yellow, the path is colored across the spectrum to show the relative step ordering, and the final square is highlighted in red.

Cf. A343356, A316667, A323714, A323808, A329519, A329520, A335844.

A343389 The ordered square-spiral numbers visited by the knight in A343388.

Original entry on oeis.org

1, 24, 11, 4, 9, 6, 15, 2, 7, 46, 21, 72, 75, 42, 19, 38, 105, 202, 151, 104, 147, 262, 199, 102, 67, 36, 61, 32, 3, 28, 51, 124, 85, 128, 53, 30, 59, 96, 141, 250, 189, 316, 251, 392, 315, 474, 563, 660, 769, 1006, 767, 658, 879, 762, 555, 462, 553, 756, 873, 998, 761, 556, 381, 460, 305

Offset: 1

Scott R. Shannon, Apr 13 2021

This is the ordered square-spiral numbers visited by a knight on a square spiral as numbered in A343388. See that sequence for further details.

Scott R. Shannon, Image showing the 359 visited squares. The spiral is numbered with the ordered spiral numbers. The starting square is highlighted in white, the visited squares in yellow, the path is colored across the spectrum to show the relative step ordering, and the final square is highlighted in red.

Cf. A343388, A343356, A316667, A323714, A323808, A329519, A329520, A335844.

cp's OEIS Frontend

A316667 Squares visited by a knight moving on a spirally numbered board always to the lowest available unvisited square.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A323809 Squares visited by a knight on a spirally numbered board, moving always to the lowest available unvisited square, or one step back if no unvisited square is available.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A323714 Squares where knight moving to a lowest unvisited square on a spirally numbered board will have no available moves.

Views

Author

Keywords

Comments

Links

Crossrefs

A323810 Squares visited by a knight on a diagonally numbered board and moving to the lowest available unvisited square at each step and if no unvisited squares are available move one step back.

Views

Author

Keywords

Comments

Links

Crossrefs

A323811 Squares visited by a knight on a diagonally numbered board and moving to the lowest available unvisited square at each step and if no unvisited squares are available move one step back.

Views

Author

Keywords

Comments

Links

Crossrefs

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A336208 Squares visited by a knight on a square-spiral numbered board and moving to the lowest available unvisited square at each step, where the step is not in the same direction as the previous step.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A343385 The ordered square spiral numbers visited by the knight in A343356.

Views

Author

Keywords

Comments

Links

Crossrefs

A343389 The ordered square-spiral numbers visited by the knight in A343388.

Views

Author

Keywords

Comments

Links

Crossrefs