A316328 -id:A316328 - cp's OEIS frontend

A323469 On a spirally numbered square grid, with labels starting at 1, this is the number of steps that a (1,n) leaper makes before getting trapped, or -1 if it never gets trapped.

-1, 2016, 3723, 13103, 14570, 26967, 101250, 158735, 132688, 220439, 144841, 646728, 350720, 66183, 75259, 248764, 118694, 307483, 238208, 189159, 139639, 183821, 151016, 171076, 114187, 262235, 178612, 257632, 124475, 178862, 143674, 196795, 60707, 309820

Offset: 1

N. J. A. Sloane, Jan 28 2019

sign

A (1,2) leaper is a chess knight.

a(2)-a(5) were computed by Daniël Karssen.

Rémy Sigrist, Table of n, a(n) for n = 1..1000
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

The sequences involved in this set of related sequences are A316884, A316967, A316667, A316328, A317106, A317105, A317416, A317415, A317438, A317437, and A323469, A323470, A323471, A323472.

More terms from Rémy Sigrist, Jan 29 2019

A323471 On a spirally numbered square grid, with labels starting at 1, this is the number of the last cell that a (1,n) leaper reaches before getting trapped, or -1 if it never gets trapped.

Original entry on oeis.org

-1, 2084, 7081, 10847, 25963, 22421, 202891, 142679, 252953, 188501, 257479, 604328, 667827, 57217, 115497, 231930, 203331, 283651, 426851, 153521, 231299, 142267, 236487, 149872, 204527, 215033, 285983, 188082, 153461, 128802, 213853, 202259, 94967, 224778

Offset: 1

N. J. A. Sloane, Jan 28 2019

sign

A (1,2) leaper is a chess knight.

a(2)-a(5) were computed by Daniël Karssen.

Rémy Sigrist, Table of n, a(n) for n = 1..1000
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

The sequences involved in this set of related sequences are A316884, A316967, A316667, A316328, A317106, A317105, A317416, A317415, A317438, A317437, and A323469, A323470, A323471, A323472.

More terms from Rémy Sigrist, Jan 29 2019

A323808 Squares visited by a knight on a spirally 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, 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, 39, 66, 63

Offset: 1

Daniël Karssen, Jan 28 2019

This is an infinite extension of A316667 with which it agrees for the first 2016 terms. - N. J. A. Sloane, Jan 28 2019

			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
See A323809 for examples where "backtracking" happens. - _M. F. Hasler_, Nov 06 2019

Daniël Karssen, Table of n, a(n) for n = 1..100000
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).

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

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

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

A326916 Trajectory of the knight's tour for choice of the square with the lowest digit, then closest to the origin, then first in the spiral.

Original entry on oeis.org

0, 11, 14, 31, 28, 51, 10, 13, 34, 95, 190, 247, 312, 385, 244, 133, 242, 239, 376, 301, 372, 233, 370, 295, 232, 173, 228, 367, 230, 171, 226, 223, 358, 285, 220, 355, 282, 217, 352, 283, 218, 115, 44, 73, 20, 71, 40, 17, 36, 15, 18, 3, 12, 1, 22, 75, 46, 117, 48, 77, 24, 79, 50, 81, 118, 221, 286, 225, 292, 229, 296, 451, 298, 235

Offset: 0

M. F. Hasler, Oct 21 2019

A variant of Angelini's "Kneil's Knumberphile Knight", inspired by Sloane's "The Trapped Knight", cf. A316328 and links:
Consider an infinite chess board with squares numbered along the infinite square spiral starting with 0 at the origin (as in A174344, A274923 and A296030). The squares are filled with successive digits of the integers: 0, 1, 2, ..., 9, 1, 0, 1, 1, ... (= A007376 starting with 0). The knight moves at each step to the yet unvisited square with the lowest digit on it, and in case of a tie, the one closest to the origin, first by Euclidean distance, then by appearance on the spiral (i.e., number of the square). This sequence lists the number of the square visited in the n-th move, if the knight starts at the origin, viz a(0) = 0.
It turns out that following these rules, the knight gets trapped at the 1070th move, when he can't reach any unvisited square.
See A326918 for the sequence of visited digits, given as A007376(a(n)).
Many squares, e.g., 2: (1,1), 4: (-1,1), 5: (-1,0), 6: (-1,-1), 7: (0,-1), 8: (1,-1), 9: (2,-1), ..., will never be visited, even in the infinite extension of the sequence where the knight can move back if it gets trapped, in order to resume with a new unvisited square, as in A323809. - M. F. Hasler, Nov 08 2019

M. F. Hasler, Table of n, a(n) for n = 0..1069
Eric Angelini, Kneil's Knumberphile Knight, Cinquante signes, May 04 2019.
Eric Angelini, Kneil's Knumberphile Knight, Cinquante signes, May 04 2019. [Cached copy, pdf file, with permission]
M. F. Hasler, Knight tours, OEIS wiki, Nov. 2019.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

Cf. A326918; A316328, A316667; A326924, A326922; A328908, A328928; A328909, A328929; A326413, A328698.

Cf. A174344, A274923, A296030; A007376.

{L326916=List(0) /* list of terms */; U326916=1 /* bitmap of used squares */; local( K=vector(8, i, [(-1)^(i\2)<<(i>4), (-1)^i<<(i<5)])/* knight moves */, 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]), 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), val(x, p=pos(x[1],x[2]))=if(bittest(U326916, p), oo, [A007376(p), norml2(x), p])); iferr( for(n=1,oo, my(x=coords(L326916[n])); U326916+=1<A326916(n)=L326916[n+1]} \\ Requires function A007376; defines function A326916.

A323470 On a spirally numbered square grid, with labels starting at 0, this is the number of the final step that a (1,n) leaper makes before getting trapped, or -1 if it never gets trapped.

Original entry on oeis.org

-1, 2015, 3722, 13102, 14569, 26966, 101249, 158734, 132687, 220438, 144840, 646727, 350719, 66182, 75258, 248763, 118693, 307482, 238207, 189158, 139638, 183820, 151015, 171075, 114186, 262234, 178611, 257631, 124474, 178861, 143673, 196794, 60706, 309819

Offset: 1

N. J. A. Sloane, Jan 28 2019

sign

A (1,2) leaper is a chess knight.

a(2)-a(5) were computed by Daniël Karssen.

Rémy Sigrist, Table of n, a(n) for n = 1..1000
Rémy Sigrist, C++ program for A323470
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

The sequences involved in this set of related sequences are A316884, A316967, A316667, A316328, A317106, A317105, A317416, A317415, A317438, A317437, and A323469, A323470, A323471, A323472.

More terms from Rémy Sigrist, Jan 29 2019

A323472 On a spirally numbered square grid, with labels starting at 0, this is the number of the last cell that a (1,n) leaper reaches before getting trapped, or -1 if it never gets trapped.

Original entry on oeis.org

-1, 2083, 7080, 10846, 25962, 22420, 202890, 142678, 252952, 188500, 257478, 604327, 667826, 57216, 115496, 231929, 203330, 283650, 426850, 153520, 231298, 142266, 236486, 149871, 204526, 215032, 285982, 188081, 153460, 128801, 213852, 202258, 94966, 224777

Offset: 1

N. J. A. Sloane, Jan 28 2019

sign

A (1,2) leaper is a chess knight.

a(2)-a(5) were computed by Daniël Karssen.

Rémy Sigrist, Table of n, a(n) for n = 1..1000
Rémy Sigrist, Figure showing the complete figure for a (1, 624) leaper (where the color is function of the time)
Rémy Sigrist, C++ program for A323472
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

The sequences involved in this set of related sequences are A316884, A316967, A316667, A316328, A317106, A317105, A317416, A317415, A317438, A317437, and A323469, A323470, A323471, A323472.

More terms from Rémy Sigrist, Jan 29 2019

A306291 List of possible numbers for the final 'trapped' square of a knight moving on an infinitely large 2-dimensional spirally numbered board starting from any square.

Original entry on oeis.org

104, 125, 149, 150, 215, 235, 247, 260, 261, 262, 266, 277, 295, 311, 329, 330, 365, 368, 369, 385, 389, 404, 406, 408, 424, 425, 432, 445, 448, 467, 469, 489, 490, 494, 495, 512, 518, 534, 535, 536, 556, 557, 558, 561, 569, 580, 581, 582, 583, 586, 588, 604, 605, 606, 629, 631, 632, 634, 655, 659

Offset: 1

Scott R. Shannon, Feb 04 2019

This is a complete list of all the possible ending 'trapped' square values for the knight (2 by 1 leaper) starting from any square. The list has 1518 values - the knight starting from any square on the infinite board will eventually be trapped on a square with one of these numbers.
I do not have a proof this is the complete list of all ending values but I believe it is correct. I have checked every knight starting square up to 100000 and they all end on one of these 1518 squares. I then check further out to 110000 and ensure these paths always move inwards once they pass the square of values which contains the 100000 value, and check they do not move outwards again passed this square. As every knight sequence out to infinity would have to cross/land between this 100000 to 110000 group of values (as they are attracted toward square 1 due to their lowest-available-value preference), and as all values have been checked inside these, it implies all knight paths with starting square values out to infinity eventually end on this list of 1518 squares.
Also note this is the ordered sequence of all 1518 squares - the initial value found starting the knight at square 1 is 2084.

			The ending square for the knight starting on square with value 1 is 2084 (see A316667). The first starting square value to end on square 104 (the smallest value) is 175. The first starting square value to end on square 23134 (the largest value) is 11509.  Testing various upper limits has shown the square with number 404 is the most likely square for any random starting square to end on (about 8% of all sequences end on it). The complete list of 1518 end squares can be generated by checking all starting squares from 1 up to 17390 (which produces the 1518th different end square of value 16851).

Scott R. Shannon, Table of n, a(n) for n = 1..1518
Scott R. Shannon, Stripped down Java code for the sequence
Scott R. Shannon, Plot of all 1518 ending squares. The yellow line indicates the boundary of the 110000 starting values used in the generation of this data. In this spiral the square with value 2 is directly above the value 1 start square (green dot). The red dot is the square with value 404 (the most likely end value square).
Scott R. Shannon, Path for knight starting at square 175. The trapped square has value 104 - the smallest trapped square value. 8 Blue dots have been added around the final square to show all positions have been visited.
Scott R. Shannon, Path for knight starting at square 11509. The trapped square has value 23134 - the largest trapped square value. 8 Blue dots have been added around the final square to show all positions have been visited.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

The sequences involved in this set of related sequences are A316884, A316967, A316667, A316328, A317106, A317105, A317416, A317415, A317438, A317437, and A323469, A323470, A323471, A323472.

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.

cp's OEIS Frontend

A323469 On a spirally numbered square grid, with labels starting at 1, this is the number of steps that a (1,n) leaper makes before getting trapped, or -1 if it never gets trapped.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A323471 On a spirally numbered square grid, with labels starting at 1, this is the number of the last cell that a (1,n) leaper reaches before getting trapped, or -1 if it never gets trapped.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A323808 Squares visited by a knight on a spirally 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

Examples

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

A326916 Trajectory of the knight's tour for choice of the square with the lowest digit, then closest to the origin, then first in the spiral.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A323470 On a spirally numbered square grid, with labels starting at 0, this is the number of the final step that a (1,n) leaper makes before getting trapped, or -1 if it never gets trapped.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A323472 On a spirally numbered square grid, with labels starting at 0, this is the number of the last cell that a (1,n) leaper reaches before getting trapped, or -1 if it never gets trapped.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A306291 List of possible numbers for the final 'trapped' square of a knight moving on an infinitely large 2-dimensional spirally numbered board starting from any square.

Views

Author

Keywords

Comments

Examples

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