A323471 -id:A323471 - 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

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.

A306308 Table read by rows: the end square loops for a trapped knight moving on an infinitely large 2-dimensional spirally numbered board starting from any square.

Original entry on oeis.org

404, 3328, 2666, 1338, 736, 1535, 2168, 406, 2444, 2945, 2245, 605, 684, 2663, 2312, 3323, 935, 910

Offset: 1

Scott R. Shannon, Feb 05 2019

Construction: with a knight (a (1,2)-leaper) on an infinite spiral numbered board moving to the lowest numbered unvisited square (see A316884), start the knight on any square and continue moving it until it is trapped. Then start an entirely new sequence starting the knight at the same square at which it was previously trapped. Continue this process until the square at which the knight is trapped has occurred previously, indicating an end square loop. All starting squares for the knight on the infinite board will eventually lead to the knight path falling into one of the 3 end square loops listed here.

As the total number of squares in which the knight can be trapped is finite (see A306291), we expect there to be a finite number of end square loops - in theory, only those values (1518 is all) need to be checked when searching for an end square loop. However, all starting square values up to 302500 have been checked to determine into which of the 3 found loops the knight eventually falls. The 13-member loop with 406 as its lowest number is found to be the dominant loop, with about 89.6% of all initial starting squares going to it. The other 10.4% mostly go to the 3-member loop with 404 as its lowest number, with a decreasingly small remainder going to the 2-member loop with 910 as it lowest number. The attached 3-color image showing the start-value-to-loop mapping shows that the pattern of starting square to end square loops becomes very regular away from the center of the board.

			The 3 end square loops are:
1: 404, 3328, 2666
2: 1338, 736, 1535, 2168, 406, 2444, 2945, 2245, 605, 684, 2663, 2312, 3323
3: 935, 910
Starting the knight from the square 1 leads to the first 3-member loop after two iterations: the sequence of end squares is 2084, 404, 3328, 2666, 404, ... . Starting from the square 2 leads to the second (13-member) loop after ten iterations: the sequence is 711, 632, 4350, 3727, 3610, 7382, 2411, 4632, 4311, 1338, ... . The third (2-member) loop is not seen until the knight starts from square 284, the sequence being entered after two iterations via 1168, 935, 910, 935, ... .

Scott R. Shannon, Square positions for the 3 loops. The red line connects the 3 points of the first loop, the blue line connects the 13 points of the second loop, and the green line connects the 2 points of the third loop. The white point marks the central square with number 1.
Scott R. Shannon, Starting square to loop mapping. A plot of the first 302500 starting squares mapped via color to the end square loop into which the corresponding knight path eventually falls: red is the first (3-member) loop, blue the second (13-member) loop, green the third (2-member) loop. The white point marks the central square with number 1 for clarity (it actually falls into the red first loop).
Scott R. Shannon, The knight's path when starting at square 910. Showing path one of the 2-member loop - the green square is the starting square 910, the red square is the end square 935.
Scott R. Shannon, The knight's path when starting at square 935. Showing path two of the 2-member loop - the green square is the starting square 935, the red square is the end square 910.
Scott R. Shannon, Stripped down Java code to produce the loop values.
N. J. A. Sloane and Brady Haran, The Trapped Knight Numberphile video (2019).

Cf. A306291, A316884, A316967, A316667, A316328, A317106, A317105, A317416, A317415, A317438, A317437, and A323469, A323470, A323471, A323472.

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

Original entry on oeis.org

2016, 4634, 1888, 4286, 1796, 3487, 3984, 7796, 5679, 5961, 7560, 7748, 9646, 17577, 13023, 23988, 19620, 14361, 20975, 25731, 40503, 31217, 39468, 44026, 31047, 75831, 62593, 70020, 69960, 65902, 79304, 64266, 66381, 62110, 72787, 122490, 139654, 117203

Offset: 1

N. J. A. Sloane, Apr 30 2021

nonn

As in all these sequences (cf. A316667), the knight or leaper must always move to the lowest-numbered unvisited square.

Andrew Trevorrow, Posting to Math Fun Mailing List, Apr 29 2021.

Rémy Sigrist, Table of n, a(n) for n = 1..1000
Rémy Sigrist, Colored representation of the squares visited for n = 1000
Rémy Sigrist, C++ program for A343178

Cf. A316667, A323469, A323471, A343179.

More terms from Rémy Sigrist, Apr 30 2021

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

Original entry on oeis.org

2084, 4698, 1164, 6500, 1202, 1383, 1952, 6338, 1869, 3743, 5280, 3626, 4522, 14191, 8313, 23750, 10852, 5967, 6601, 16191, 24571, 33535, 20978, 21552, 10661, 36193, 51587, 69754, 17618, 33186, 36548, 33424, 19389, 19670, 21097, 50306, 25040, 51385, 50256

Offset: 1

N. J. A. Sloane, Apr 30 2021

nonn

As in all these sequences (cf. A316667), the knight or leaper must always move to the lowest-numbered unvisited square.

Andrew Trevorrow, Posting to Math Fun Mailing List, Apr 29 2021.

Rémy Sigrist, Table of n, a(n) for n = 1..1000
Rémy Sigrist, C++ program for A343179

Cf. A316667, A323469, A323471, A323750, A343178.

More terms from Rémy Sigrist, Apr 30 2021

A352731 On a diagonally 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 when moving to the lowest available unvisited square, or -1 if it never gets trapped.

Original entry on oeis.org

-1, 1378, -1, 595, 66, 36, 153, 758, 1185, 78, 1732, 171, 2510, 2094, 1407, 253, 630, 210, 780, 2385, 1326, 300, 1225, 990, 2800, 406, 3267, 4333, 4124, 528, 4309, 741, 5951, 666, 2701, 903, 30418, 820, 3321, 1081, 4186, 990, 8299, 2775, 4560, 1176, 4753, 39951, 5778

Offset: 1

Andrew Smith, Mar 30 2022

sign

A (1,2) leaper is a chess knight. (1,1) and (1,3) leapers both never get trapped. This is understandable for the (1,1) leaper but not so much for the (1,3) which does get trapped on the spirally numbered board (see A323471). Once the (1,3) leaper reaches 39 it then performs the same set of 4 moves repeatedly, meaning that it never gets trapped.

Cf. A323469, A323471, A352730.

# reformatted by R. J. Mathar, 2023-03-29
class A352731():
    def _init_(self,n) :
        self.n = n
        self.KM=[(n, 1), (1, n), (-1, n), (-n, 1), (-n, -1), (-1, -n), (1, -n), (n, -1)]
    @staticmethod
    def _idx(loc):
        i, j = loc
        return (i+j-1)*(i+j-2)//2 + j
    def _next_move(self,loc, visited):
        i, j = loc
        moves = [(i+io, j+jo) for io, jo in self.KM if i+io>0 and j+jo>0]
        available = [m for m in moves if m not in visited]
        return min(available, default=None, key=lambda x: A352731._idx(x))
    def _aseq(self):
        locs = [[], []]
        loc, s, turn, alst = [(1, 1), (1, 1)], {(1, 1)}, 0, [1]
        m = self._next_move(loc[turn], s)
        while m != None:
            loc[turn], s, turn, alst = m, s|{m}, 0 , alst + [A352731._idx(m)]
            locs[turn] += [loc[turn]]
            m = self._next_move(loc[turn], s)
            if len(s)%100000 == 0:
                print(self.n,'{steps} moves in'.format(steps = len(s)))
        return alst
    def at(self,n) :
        if n == 1 or n == 3:
            return -1
        else:
            return self._aseq()[-1]
for n in range(1,40):
    a352731 = A352731(n)
    print(a352731.at(n))

A306421 End squares for a trapped knight moving on a spirally numbered 2D grid where each square can be visited n times.

Original entry on oeis.org

2084, 124561, 1756923, 21375782, 48176535, 128322490, 196727321, 230310289, 606217402, 2856313870, 244655558, 659075420, 586292888, 1646774611, 1018215514, 719687377, 564513339, 2779028614, 298995630, 1641747842, 414061107, 1467655587, 584309414, 1584716050

Offset: 1

Scott R. Shannon, Feb 14 2019

nonn

For a knight (a (1,2) leaper) starting at square 1 and moving on a spirally numbered 2D grid to the lowest-numbered available square at each step (see A316667), a(n) is the number of the square at which the knight is trapped if it is allowed to visit each square no more than n times -- the knight is not trapped until each of the 8 surrounding squares to which it can leap has been visited n times. The choice of the square to which it goes at each step is determined solely by the square with the lowest spiral number, as long as it has been visited fewer than n times. This is an infinite sequence, although end squares beyond a(35) are currently unknown.

			For n = 1, the knight becomes trapped at square 2084 (see A316667). The following table gives the corresponding values for n = 1 through 35:
.
     | Square at which | Number of steps
     |  the knight is  | before the
   n |     trapped     | knight is trapped
  ---+-----------------+--------------
   1 |         2084    |          2016 (A316667)
   2 |       124561    |        244273
   3 |      1756923    |       4737265
   4 |     21375782    |      98374180
   5 |     48176535    |     258063291
   6 |    128322490    |     836943142
   7 |    196727321    |    1531051657
   8 |    230310289    |    1897092533
   9 |    606217402    |    5253106114
  10 |   2856313870    |   27296872250
  11 |    244655558    |    2772304666
  12 |    659075420    |    8437814958
  13 |    586292888    |    7875951360
  14 |   1646774611    |   24511621133
  15 |   1018215514    |   15493169264
  16 |    719687377    |   11643899003
  17 |    564513339    |    9593491769
  18 |   2779028614    |   49835086546
  19 |    298995630    |    5734502340
  20 |   1641747842    |   33370972720
  21 |    414061107    |    8844741817
  22 |   1467655587    |   32843399937
  23 |    584309414    |   13583967470
  24 |   1584716050    |   37945957450
  25 |   2544445470    |   62083869640
  26 |   4796115990    |  125967045044
  27 |   1881606731    |   51291895045
  28 |   1321212795    |   37635024035
  29 |   6693611092    |  196994700434
  30 |    687619472    |   19985943874
  31 |   1495794139    |   45392651369
  32 |   6677258413    |  213836002227
  33 |   6451059544    |  219770103702
  34 |   7958333435    |  277128625469
  35 |  13924943879    |  485324576539

Scott R. Shannon, Simplified Java code for producing the series
Scott R. Shannon, Visited positions for n=3. For clarity only the visited positions are shown. Blue=3 visits, Green=2 visits, White=1 visit. Red is the final square (near top right corner). Note that the internal positions are all visited the maximum 3 times, and that the overall shape becomes an 'indented square' -- this pattern becomes more pronounced as n increases. Likewise the maximum visited x and y distances relative to the central square approach equality as n increases e.g. for n=35 both the maximum x and y visited distances are 59855.
N. J. A. Sloane and Brady Haran, The Trapped Knight, Numberphile video (2019)

Cf. A316884, A316967, A316667, A316328, A317106, A317105, A317416, A317415, A317438, A317437.

Cf. A323469, A323470, A323471, A323472.

A352730 On a diagonally numbered square grid, with labels starting at 1, this is the number of steps that a (1,n) leaper makes before getting trapped when moving to the lowest available unvisited square, or -1 if it never gets trapped.

Original entry on oeis.org

-1, 2402, -1, 1552, 287, 388, 417, 1593, 639, 1136, 1785, 3090, 2299, 2341, 1833, 4052, 2237, 3012, 3069, 6843, 5543, 3000, 5161, 11722, 6895, 3578, 8047, 19739, 9671, 4156, 8391, 21424, 15129, 4734, 8609, 32690, 19895, 5312, 10019, 42710, 21195, 5890, 12309, 53764, 34489, 6468, 19527, 55911, 23475

Offset: 1

Andrew Smith, Mar 30 2022

sign

A (1,2) leaper is a chess knight. (1,1) and (1,3) leapers both never get trapped. This is understandable for the (1,1) leaper but not so much for the (1,3) which does get trapped on the spirally numbered board (see A323469). Once the (1,3) leaper reaches 39 it then performs the same set of 4 moves repeatedly, meaning that it never gets trapped.

Cf. A323469, A323471, A352731.

n = 2
KM = [(n, 1), (1, n), (-1, n), (-n, 1), (-n, -1), (-1, -n), (1, -n), (n, -1)]
def idx(loc):
    i, j = loc
    return (i + j - 1) * (i + j - 2) // 2 + j
def next_move(loc, visited):
    i, j = loc
    moves = [(i + io, j + jo) for io, jo in KM if i + io > 0 and j + jo > 0]
    available = [m for m in moves if m not in visited]
    return min(available, default=None, key=lambda x: idx(x))
def aseq():
    locs = [[], []]
    loc, s, turn, alst = [(1, 1), (1, 1)], {(1, 1)}, 0, [1]
    m = next_move(loc[turn], s)
    while m != None:
        loc[turn], s, turn, alst = m, s | {m}, 0, alst + [idx(m)]
        locs[turn] += [loc[turn]]
        m = next_move(loc[turn], s)
        if len(s) % 10000 == 0:
            print('{steps} moves in'.format(steps = len(s)))
    return alst
print(aseq())

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

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

A306308 Table read by rows: the end square loops for a trapped knight moving on an infinitely large 2-dimensional spirally numbered board starting from any square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A352731 On a diagonally 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 when moving to the lowest available unvisited square, or -1 if it never gets trapped.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

A306421 End squares for a trapped knight moving on a spirally numbered 2D grid where each square can be visited n times.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A352730 On a diagonally numbered square grid, with labels starting at 1, this is the number of steps that a (1,n) leaper makes before getting trapped when moving to the lowest available unvisited square, or -1 if it never gets trapped.

Views

Author

Keywords

Comments