A323561 -id:A323561 - cp's OEIS frontend

A323562 Number of rooted self-avoiding king's walks on an infinite chessboard trapped after n moves.

8, 200, 2446, 21946, 169782, 1205428, 8119338, 52862872, 336465352, 2108185746

Offset: 8

Hugo Pfoertner, Jan 17 2019

The first step is either (0,0)->(1,0) or (0,0)->(1,1). Rotated paths are not counted separately.
The average number of moves of a self-avoiding random walk of a king on an infinite chessboard to self-trapping is 209.71. The corresponding number of moves for paths with forbidden crossing (A323141) is 69.865.
a(n)=0 for n<8.

			a(8) = 8, because the following 8 walks of 8 moves of a king starting at S with a first move (0,0)->(1,0) visit all neighbors of the trapping location T. The starting point itself is also blocked. There are no such shortest walks with first move (0,0)->(1,1).
.
  o <-- o <-- o   o     o <-- o   o --> o --> o   o <-- o <-- o
  |           ^   ^ \ /       ^   ^           |   |           ^
  v           |   | / \       |   |           v   v           |
  o --> T     o   o     T     o   o     T     o   o     T     o
              ^               ^     \    \    |   |   /       ^
              |               |       \    \  v   v /         |
  S --> o --> o   S --> o --> o   S --> o     o   o     S --> o
.
  S --> o --> o   S --> o --> o   S --> o     o   o     S --> o
              |               |       /    /  ^   ^ \         |
              v               v     /    /    |   |   \       v
  o --> T     o   o     T     o   o     T     o   o     T     o
  ^           |   | \ /       |   |           ^   ^           |
  |           v   v / \       v   v           |   |           v
  o <-- o <-- o   o     o <-- o   o --> o --> o   o <-- o <-- o
- _Hugo Pfoertner_, Jul 23 2020

Hugo Pfoertner, Probability density for the number of moves to self-trapping, (2019).

Cf. A077482, A322831, A323141, A323560, A323561.

A335856 Squares visited by a chess king on a spirally numbered infinite board where the king moves to the adjacent unvisited square containing the lowest prime number. If no such square is available it chooses the lowest-numbered adjacent unvisited square.

Original entry on oeis.org

1, 2, 3, 11, 29, 13, 31, 59, 32, 14, 4, 5, 17, 37, 67, 103, 149, 104, 66, 38, 18, 19, 7, 23, 47, 79, 48, 24, 8, 6, 20, 41, 71, 43, 73, 109, 72, 42, 21, 22, 44, 45, 46, 76, 75, 113, 74, 112, 110, 111, 157, 211, 271, 209, 269, 337, 267, 205, 151, 107, 69, 39, 40, 68, 105, 106, 70, 108

Offset: 1

Scott R. Shannon, Jun 27 2020

This sequences gives the numbers of the squares visited by a chess king moving on a square-spiral numbered board where the king starts on the 1 numbered square and at each step moves to the adjacent unvisited square containing the lowest prime number. If no adjacent unvisited square contains a prime number then the square with the lowest spiral number is chosen. Note that if the king simply moves to the lowest unvisited number the sequence will be infinite as the king will just follow the square spiral path.
The sequence is finite. After 719 steps the square with number 437 is visited, after which all adjacent neighboring squares have been visited.
Of the 719 visited squares 165 contain prime numbers while 554 contain composites. As the odd numbers are diagonally adjacent in the square spiral the king's path will contain many diagonal steps, often taking numerous diagonal steps is succession - see the attached link image.
The largest visited square is a(709) = 1367. The lowest unvisited square is 33.
The 719 steps until self-trapping occurs are significantly larger than the expected average of 210 moves to self-trapping for a random walk of the king on an infinite chessboard. See the link to the probability density graphs in A323562. - Hugo Pfoertner, Jul 19 2020
When the grid points are labeled starting with 0 at the origin, the king gets trapped after 171 moves at (3,0), after going as far as (10,-11) to the south-east and (-8,7) and (-5,8) to the north-east, see A383183. - M. F. Hasler, May 13 2025

			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 for the king.
a(2) = 2. The four unvisited squares around a(1) the king can move which contain prime numbers are 2,3,5,7. Of those 2 is the lowest.
a(4) = 11. The two unvisited squares around a(3) = 3 the king can move to which contain prime numbers are 11 and 13. Of those 11 is the lowest.
a(9) = 32. There are no unvisited squares around a(8) = 59 which contain prime numbers. The seven other unvisited squares are numbered 32,33,58,60,93,94,95. Of those 32 is the lowest.

M. F. Hasler, Table of n, a(n) for n = 1..720 (complete sequence), May 13 2025
Scott R. Shannon, Image showing the 719 steps of the path. A green dot marks the starting square and a red dot the final square with number 437. The red dot is surrounded by eight blue dots to show the occupied neighboring squares. A yellow dot marks the smallest unvisited square with number 33.

Cf. A333714, A333713, A335816, A336038, A336092, A316667.
Cf. A174344, A274923, A272763, A323561, A323562.
Cf. A000040 (the primes), A010051 (characteristic function of the primes).

from sympy import isprime # or use A010051
def square_number(z): return int(4*y**2-y-x if (y := z.imag) >= abs(x := z.real)
    else 4*x**2-x-y if -x>=abs(y) else (4*y-3)*y+x if -y>=abs(x) else (4*x-3)*x+y)
def A335856(n, moves=(1, 1+1j, 1j, 1j-1, -1, -1-1j, -1j, 1-1j)):
    if not hasattr(A:=A335856, 'terms'): A.terms=[1]; A.pos=0
    while len(A.terms) < n:
        try: move = min((1-isprime(s), s, z) for d in moves if
                        (s := square_number(z := A.pos+d)+1)not in A.terms)
        except ValueError:
            raise IndexError(f"Sequence has only {len(A.terms)} terms")
        A.terms.append(move[1]); A.pos = move[2]
    return A.terms[n-1]
A335856(999) # gives IndexError: Sequence has only 720 terms
A335856.terms # shows all 720 terms; append [:N] to see only N terms
# M. F. Hasler, May 13 2025

Name edited by Peter Munn, May 11 2025

More terms (complete sequence) from M. F. Hasler, May 13 2025

A376609 a(n) is the numerator of the expected number of random moves of a chess king to reach a position outside an nXn chessboard, starting in one of the corners.

Original entry on oeis.org

1, 8, 72, 46, 23747, 94968, 12161644, 158536576, 165181795263, 1779861954248, 60921563004721184, 136512657826472304, 38548316743830620183051, 581371653539561314, 2630585854108441990301102856, 120104329127347395409698056, 5092493809189909792181005355935991197, 6666722670813237580783418910187983288

Offset: 1

Hugo Pfoertner, Oct 03 2024

The king visits the Moore neighborhood (see A272763). The piece does not pay attention to its position and will fall off the board if it makes a move beyond the edge of the board.

			1, 8/5, 72/35, 46/19, 23747/8723, 94968/31879, 12161644/3797647, 158536576/46627015, 165181795263/46174521031, ...
Approximately 1, 1.6, 2.057, 2.421, 2.722, 2.979, 3.202, 3.400, 3.577, 3.738, ...

Hugo Pfoertner, Table of n, a(n) for n = 1..45
Hugo Pfoertner, Plot of A376609(n)/A376610(n) vs n, using Plot 2.
Hugo Pfoertner, Results of a simulation of 10^9 walks on the 8X8 board.

A376610 are the corresponding denominators.
A376606 and A376607 are similar for a rook walk with unit steps.
A376736 and A376737 are similar for a chess knight.
Cf. A140518, A272763, A323140, A323561, A323562.

\\ Uses function droprob from A376606
kingmoves = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]];
a376609(n) = numerator(droprob(n,kingmoves,8))

A355844 a(n) is the number of different self-avoiding (n-1)-move routes for a king on an empty n X n chessboard.

Original entry on oeis.org

1, 12, 160, 1764, 17280, 156484, 1335984, 10899404, 85743256, 654854660, 4880419048, 35632524244, 255652444992, 1806891645852, 12605286082848, 86939096972284, 593610191062680, 4016965725987052, 26965990393104248

Offset: 1

Frank Hollstein, Jul 18 2022

			n = 3
The squares are numbered as follows:
  0 1 2
  3 4 5
  6 7 8
By symmetry, only the routes starting from a corner square (e.g., square 0), one of the 4 side squares (e.g., square 1), and the 1 center square (square 4) need to be considered.
.
15 routes starting at square 0:
  012 015 014 013
  041 042 043 045 046 047 048
  031 034 036 037
.
19 routes starting at square 1:
  103 104
  124 125
  130 134 136 137
  140 142 143 145 146 147 148
  152 154 157 158
.
24 routes starting at square 4:
  401 403
  410 412 413 415
  421 425
  430 431 436 437
  451 452 457 458
  463 467
  473 475 476 478
  485 487
.
Total number of routes: 4*15 + 4*19 + 1*24 = 60 + 76 + 24 = 160.

Cf. A323561, A323562, A355127.

a(12)-a(15) from Martin Ehrenstein, Sep 22 2022

a(16)-a(19) from Martin Ehrenstein, Sep 27 2022

cp's OEIS Frontend

A323562 Number of rooted self-avoiding king's walks on an infinite chessboard trapped after n moves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A335856 Squares visited by a chess king on a spirally numbered infinite board where the king moves to the adjacent unvisited square containing the lowest prime number. If no such square is available it chooses the lowest-numbered adjacent unvisited square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A376609 a(n) is the numerator of the expected number of random moves of a chess king to reach a position outside an nXn chessboard, starting in one of the corners.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A355844 a(n) is the number of different self-avoiding (n-1)-move routes for a king on an empty n X n chessboard.

Views

Author

Keywords

Examples

Crossrefs

Extensions