A329519 -id:A329519 - cp's OEIS frontend

A329520 a(n) is the number of completed steps before being trapped for a knight moving on a square-spiral numbered board where the knight moves to an unvisited square with the lowest spiral number and with n or fewer visited neighbors. It only moves to squares with n+1 or more visited neighbors when no other squares are available, and if two or more such squares are present it chooses the square with the fewest visited neighbors, then the square with the lowest spiral number if still tied.

1151, 225, 1866, 513316, 11171, 3935788, 23014, 2015

Offset: 1

Scott R. Shannon, Nov 19 2019

This sequence gives the number of completed steps for a knight before being trapped when moving on a square-spiral numbered board and at each step choosing an unvisited square one knight-leap away which has the lowest spiral number and has n or fewer visited neighboring squares. It will only move to a square with n+1 or more neighbors when no square with n or fewer neighbors is available. If it is forced to move to such squares and two or more are available, it will choose the square with the fewest neighbors. If two or more squares with the same number of neighbors exist then it will choose the square with the smallest spiral number.
For n = 8 the path is equivalent to that given in A316667. Every square will always have eight or fewer visited neighbors, thus all unvisited squares are available to move to and the one with the smallest spiral number will always be chosen. This is A316667.
The values are surprisingly diverse, and it is not immediately obvious that the smaller values of n will even have a finite path length. It seems reasonable to assume that with the knight always choosing squares with very few visited neighbors it would be constantly moving away from the origin and thus never be trapped. But the path taken shows that, with such a restrictive choice of neighboring squares, the path leaves large areas of unvisited squares as the knight moves around the board, some of these being relatively close to the origin. At some point the knight will have an open path and move to these squares, thus move toward the origin, due to its preference to choose the squares with the smallest spiral number. It is thus drawn inward where it will then be surrounded by previous visited squares and eventually trapped. This tendency to leave large areas of unvisited squares is most easily seen in the path for n = 2, see link below, which is trapped after only 225 steps.
On the other extreme the path for n = 6, see A329519, is such that very few open areas remain near the origin, but the knight is still cautious in its choice and will not move to a square where it will likely be trapped, unless no other choices exist. This leads to the knight performing an extremely long walk before eventually finding a gap in its previous paths, moving toward the origin and finally being trapped after 3935788 steps.

			a(6) = 3935788. See A329519.
a(7) = 23014. See A329518.
a(8) = 2015. See A316667.
See A316667 for the spiral board numbering.

Scott R. Shannon, The knight's path for n = 1. The knight is trapped after 1151 steps. In this and other images the first square is marked in green, the final square in red, and the eight blocking squares in blue.
Scott R. Shannon, The knight's path for n = 2. The knight is trapped after only 225 steps. The start square acts as one of the blocking squares.
Scott R. Shannon, The knight's path for n = 4. The knight is trapped after 513316 steps. In this image the cyan points indicate where the knight would have gone to a square with eight neighbors, and thus been trapped, if these were not rejected by the n = 4 cutoff. The yellow colored points indicate similar but for combined neighbor counts of five, six and seven neighbors. The final square is in the cusp of the outer edge near the 7:30 clock position.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Cf. A316667, A329518, A329519.

A329518 Squares visited by a knight moving on a square-spiral numbered board where the knight moves to an unvisited square with the lowest spiral number and with seven or fewer visited neighbors. It only moves to squares with eight visited neighbors when no other square is available.

Original entry on oeis.org

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

Scott R. Shannon, Nov 18 2019

This is a variation of A316667. The same knight move rules apply, but the knight will not move to a square which will result in it being trapped (the square will have eight visited surrounding neighbors) unless no other squares are available. If the only squares available will all result in the knight being trapped it will choose the one with the lowest board spiral number.
The sequence is finite. After 23014 steps the square with spiral number 25809 is reached after which all surrounding squares have been visited. This is the third largest possible path using the given knight-leap rules for the eight possible values of visited neighbor count. A329520 gives the other path lengths.
The sequences matches the values of A316667 for the first 2015 terms, but on the 2015th step the knight sees that square 2084 will result in it being trapped and thus chooses square 2668 instead. Along its path the knight encounters sixteen squares where it would be trapped if it had chosen the smallest numbered available square. These occurs after steps 2015, 2983, 3116, 3372, 7485, 8775, 9726, 10971, 11845, 11918, 12140, 18477, 18706, 19921, 22223, 23014. The corresponding board numbers which were rejected are given by the first fifteen values of A323714. On step 23014 there is only one square available which is it forced to move to, resulting in it being trapped on square 25809, the sixteenth entry of A323714.

			See A316667 for the spiral board numbering.

Scott R. Shannon, Table of n, a(n) for n = 1..23015
Scott R. Shannon, Image showing the 23104 steps of the knight's path. The start square is shown in green and the final square in red. All squares where the knight would have been trapped if it had chosen the lowest numbered available square are shown in yellow, along with the number of steps completed. The square it rejected at that point is shown in gray, and eight purple squares are shown around these rejected squares to show the square would have resulted in trapping. The second last square is also surrounded by eight pink squares showing that the only available square at that point was the final square which it was thus forced to move to. The final square, on the edge at about the 7 o'clock position, is surrounded by its eight blocking squares in blue.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).

Cf. A316667, A323714, A329519, A329520.

A330189 Squares visited by a knight moving on a square-spiral numbered board where the knight moves to the unvisited square with the fewest visited neighbors. In case of a tie it chooses the square with the lowest spiral number.

Original entry on oeis.org

1, 10, 3, 6, 9, 4, 7, 2, 25, 50, 79, 116, 45, 74, 71, 106, 67, 36, 61, 94, 31, 54, 89, 128, 175, 84, 81, 118, 163, 76, 113, 72, 107, 68, 37, 62, 95, 136, 59, 56, 87, 126, 83, 172, 169, 82, 171, 224, 285, 354, 431, 516, 349, 426, 275, 210, 213, 112, 157, 208, 267, 334, 263, 200, 101, 66, 63, 38, 65, 144, 193, 250, 315, 246, 137, 186, 133, 238, 183, 134, 181

Offset: 1

Scott R. Shannon (following a suggestion by M. F. Hasler), Dec 04 2019

This sequences gives the numbers of the squares visited by a knight moving on a square-spiral numbered board, as described in A316667, where at each step the knight goes to the neighbor one knight-leap away which has the fewest visited neighbors. If two or more neighbors exist with the same lowest neighbor count then, from that list of squares, the square with the lowest spiral number is chosen.
The sequence is finite. After 656 steps the square with number 273 is visited, after which all neighboring squares have been visited.
The first step where the knight has only one neighbor to choose from in the list of neighboring squares with the fewest visited neighbors is at step 39 where only neighboring square 56 has one visited neighbor. The first step where the neighboring squares all have two or more visited neighbors is at step 146 where neighboring squares 443, 533, and 535 all have two visited neighbors.
Like the walks in A329520 it is not immediately obvious that this will be a finite walk as one may believe the knight would be constantly moving away from the origin and thus never be trapped. But like in those walks, the knight here leaves gaps in its path as it moves away from the origin, which will subsequently be visited due to the knight's preference of choosing the square with the smallest spiral number when two or more squares with the same neighbor count are encountered. This draws the knight toward the origin where it will eventually be trapped.

			See A316667 for the spiral board numbering.

Scott R. Shannon, Table of n, a(n) for n = 1..657
Scott R. Shannon, Image showing the 656 steps of the knight's path. The green dot is the starting square with number 1 and the red dot the final square with number 273. The red dot is surrounded by blue dots to show the eight occupied neighboring squares. Also shown are yellow dots which indicate squares where only one square was in the list of neighboring squares with the fewest neighbors, and cyan dots which indicate squares where the minimum visited neighbor count of neighboring squares was two or more.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019).
N. J. A. Sloane (in collaboration with Scott R. Shannon), Art and Sequences, Slides of guest lecture in Math 640, Rutgers Univ., Feb 8, 2020. Mentions this sequence.

Cf. A316667, A329520, A329518, A329519.

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A329518 Squares visited by a knight moving on a square-spiral numbered board where the knight moves to an unvisited square with the lowest spiral number and with seven or fewer visited neighbors. It only moves to squares with eight visited neighbors when no other square is available.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A330189 Squares visited by a knight moving on a square-spiral numbered board where the knight moves to the unvisited square with the fewest visited neighbors. In case of a tie it chooses the square with the lowest spiral number.

Views

Author

Keywords

Comments

Examples

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