A323562 -id:A323562 - cp's OEIS frontend

A323560 Number of self-avoiding knight's paths trapped after n moves on an infinite chessboard with first move specified.

1728, 10368, 332660, 1952452

Offset: 15

Hugo Pfoertner, Jan 18 2019

The average number of moves of a self-avoiding random walk of a knight on an infinite chessboard to self-trapping is 3210. The corresponding number of moves for paths with forbidden crossing (A323131) is 45.

a(n)=0 for n<15.

			There are two (of a(15)=1728) paths of 15 moves of minimum extension 5 X 5:
  (N) b1 d2 e4 c5 a4 b2 d1 e3 d5 b4 a2 c1 e2 d4 b5 c3, and
  (N) a4 c5 e4 d2 b1 a3 b5 d4 e2 c1 a2 b4 d5 e3 d1 c3.

Hugo Pfoertner, Illustrations of the 1728 trapped paths of length 15, (2019).
Hugo Pfoertner, Probability density for the number of moves to self-trapping, (2019).

Cf. A077482, A323141, A323559, A323562.

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.

Original entry on oeis.org

71, 71, 40, 77, 45, 51, 42, 56, 49, 51, 48, 54

Offset: 3

Hugo Pfoertner, Dec 27 2018

The cases n = 3, 4, and 6 correspond to the usual self-avoiding random walks on the honeycomb net, the square lattice, and the hexagonal lattice, respectively. The other cases n = 5, 7, ... are a generalization using self-avoiding rooted walks similar to those defined in A306175, A306177, ..., A306182. The walk is trapped if it cannot be continued without either hitting an already visited (lattice) point or crossing or touching any straight line connecting successively visited points on the path up to the current point.
The result 71 for n=4 was established in 1984 by Hemmer & Hemmer.
The sequence data are based on the following results of at least 10^9 simulated random walks for each n <= 12, with an uncertainty of +- 0.004 for the average walk length:
   n  length
71.132
70.760 (+-0.001)
40.375
77.150
45.297
51.150
42.049
56.189
48.523
51.486
47.9   (+-0.2)
53.9   (+-0.2)

S. Hemmer, P. C. Hemmer, An average self-avoiding random walk on the square lattice lasts 71 steps, J. Chem. Phys. 81, 584 (1984)
Hugo Pfoertner, Examples of self-trapping random walks.
Hugo Pfoertner, Probability density for the number of steps before trapping occurs, 2018.
Hugo Pfoertner, Results for the 2D Self-Trapping Random Walk.
Alexander Renner, Self avoiding walks and lattice polymers, Diplomarbeit, Universität Wien, December 1994.

Cf. A001668, A001411, A001334, A077482, A306175, A306177, A306178, A306179, A306180, A306181, A306182.

Cf. A122223, A122224, A122226, A127399, A127400, A127401, A300665, A323141, A323560, A323562, A323699.

A323141 Number of self-trapped uncrossed king's paths on an infinite board after n steps, reduced for symmetry.

Original entry on oeis.org

0, 0, 0, 0, 2, 19, 150, 1043, 6843, 43192, 266529, 1619983, 9746883, 58220994, 345919915

Offset: 1

Hugo Pfoertner, Jan 05 2019

The average number of moves of a self-avoiding uncrossed random walk of a king on an infinite chessboard to self-trapping is 69.865+-0.008. - Hugo Pfoertner, Oct 22 2024

			a(5) = 2: There are 2 walks where the king is blocked after 5 steps, because for the diagonal moves it would have to cross its previous path.
.
  o       2       o       o       3        o
        /   \                   /   \
      /       \               /        \
    /           \           /            \
  3       5       1       4 - - - 5        2
  |     /       /                        /
  |   /       /                        /
  | /       /                        /
  4       S       o       S - - -  1       o

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

Cf. A003192, A077482, A272773, A323140, A323562.

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))

A323561 Number of rooted self-avoiding king's walks of n moves on an infinite chessboard with first move specified.

Original entry on oeis.org

2, 14, 92, 584, 3644, 22482, 137626, 837466, 5072590, 30611376, 184171252, 1105262004, 6618842522, 39564403462, 236123357538, 1407249202976, 8376673823516

Offset: 1

Hugo Pfoertner, Jan 17 2019

The first move is either (0,0) -> (1,0) or (0,0) -> (1,1). Rotated paths are not counted separately.

Cf. A001411, A212715, A272773, A323131, A323140, A323559, A323562.

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

Original entry on oeis.org

1, 12, 200, 2880, 37680, 455224, 5186888, 56471040, 593296160, 6057160296, 60407414256, 590807590672, 5684125083000, 53924502344880, 505415790232592, 4687367714152128, 43070861665247616, 392532002390446600, 3551337773634149120, 31920035670120464496

Offset: 1

Frank Hollstein, Jun 20 2022

			n = 2:
.
Numeration of squares on board:
  0 1
  2 3
.
By symmetry, the number of routes from each of the 4 starting squares is the same.
.
3 routes starting at square 0:
  01 02 03
.
Total number of routes: 4*3 = 12.
---------------------------------
n = 3:
Numeration of squares on board:
  0 1 2
  3 4 5
  6 7 8
.
Using symmetry, only the numbers of routes starting from one of the 4 corner squares (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.
.
18 routes starting at square 0:
  010 012 015 014 013
  040 041 042 043 045 046 047 048
  030 031 034 036 037
.
24 routes starting at square 1:
  101 103 104
  121 124 125
  131 130 134 136 137
  141 140 142 143 145 146 147 148
  151 152 154 157 158
.
32 routes starting at square 4:
  404 401 403
  414 410 412 413 415
  424 421 425
  434 430 431 436 437
  454 451 452 457 458
  464 463 467
  474 473 475 476 478
  484 485 487
.
Total number of routes: 4*18 + 4*24 + 1*32 = 72 + 96 + 32 = 200.

Alois P. Heinz, Table of n, a(n) for n = 1..1101

Cf. A086346, A086347, A151331, A323562.

b:= proc(n, m, x, y) option remember; `if`(n=0, 1, add(
      add((s-> `if`({i, j}={0} or min(s)<1 or max(s)>m, 0,
        b(n-1, m, s[])))([x+i, y+j]), j=-1..1), i=-1..1))
    end:
a:= n-> add(add(b(n-1, n, x, y), x=1..n), y=1..n):
seq(a(n), n=1..20);  # Alois P. Heinz, Jun 20 2022

b[n_, m_, x_, y_] := b[n, m, x, y] = If[n == 0, 1, Sum[Sum[With[{s = {x + i, y + j}}, If[Union@{i, j} == {0} || Min[s] < 1 || Max[s] > m, 0, b[n - 1, m, Sequence @@ s]]], {j, -1, 1}], {i, -1, 1}]];
a[n_] := Sum[Sum[b[n - 1, n, x, y], {x, 1, n}], {y, 1, n}];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 10 2022, after Alois P. Heinz *)

From Vaclav Kotesovec, Jul 18 2022: (Start)
Recurrence: (n-4) * (n-2) * (n-1)^2 * (6561*n^8 - 212139*n^7 + 2950263*n^6 - 23053977*n^5 + 110718549*n^4 - 334617561*n^3 + 621301485*n^2 - 647573195*n + 289741950)*a(n) = (n-2) * (98415*n^11 - 3621672*n^10 + 58904658*n^9 - 557565930*n^8 + 3401022330*n^7 - 13968918180*n^6 + 39146085342*n^5 - 74076664722*n^4 + 91284487995*n^3 - 67946473736*n^2 + 26218206060*n-3608592880)*a(n-1) - 2 * (951345*n^11 - 35042301*n^10 + 573945345*n^9 - 5517149841*n^8 + 34570186911*n^7 - 148143645873*n^6 + 442497763659*n^5 - 919659425931*n^4 + 1300075875920*n^3 - 1186236344006*n^2 + 625358201108*n-143083453680)*a(n-2) - 8 * (n-3) * (538002*n^11 - 20170701*n^10 + 335662947*n^9 - 3269686095*n^8 + 20693992482*n^7 - 89239225257*n^6 + 267100420161*n^5 - 553559634623*n^4 + 775814257936*n^3 - 696718449512*n^2 + 358050585284*n-78798884240)*a(n-3) + 64 * (n-4) * (39366*n^11 - 747954*n^10 + 1036638*n^9 + 95287104*n^8 - 1244227635*n^7 + 8077634280*n^6 - 32356061235*n^5 + 84721205046*n^4 - 145611420210*n^3 + 158260316980*n^2 - 98341752748*n + 26435972680)*a(n-4) + 512 * (n-5) * (n-3) * (118098*n^10 - 3864429*n^9 + 55834110*n^8 - 468708363*n^7 + 2528957700*n^6 - 9150957666*n^5 + 22446838206*n^4 - 36764880492*n^3 + 38348031900*n^2 - 22886883656*n + 5886448960)*a(n-5) + 8192 * (n-6) * (n-5) * (n-4) * (n-3) * (6561*n^8 - 159651*n^7 + 1648998*n^6 - 9439902*n^5 + 32737014*n^4 - 70335324*n^3 + 91203060*n^2 - 64949504*n + 19261936)*a(n-6).
a(n) ~ n^2 * 8^(n-1) * (1 - 2*sqrt(6/(Pi*n))). (End)

a(11)-a(20) from Alois P. Heinz, Jun 20 2022

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

A323560 Number of self-avoiding knight's paths trapped after n moves on an infinite chessboard with first move specified.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi*(2*k/n - 1), k = 1..n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

A323141 Number of self-trapped uncrossed king's paths on an infinite board after n steps, reduced for symmetry.

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

A323561 Number of rooted self-avoiding king's walks of n moves on an infinite chessboard with first move specified.

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A322831 Average path length to self-trapping, rounded to nearest integer, of self-avoiding two-dimensional random walks using unit steps and direction changes from the set Pi(2k/n - 1), k = 1..n-1.