A272763 -id:A272763 - cp's OEIS frontend

A272773 Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).

1, 8, 56, 360, 2240, 13696, 82808, 496656, 2961136, 17573608, 103911424, 612577272, 3602222736, 21137815952, 123811421128, 724064474968, 4228582808424

Offset: 0

Giovanni Resta, May 06 2016

The path cannot return to a lattice point nor intersect with itself (which IS allowed in A272763).

The Moore neighborhood characterizes king tours. - Rainer Rosenthal, Jan 06 2019

Cf. A272763, A001411, A323140, A323141.

# For starting point stp and list Ldir of n directions (1..8)
# construct the points of the whole path and count them.
# In order to avoid crossings consider the n midpoints, too.
# If there are 2*n+1 then the path is self-avoiding and uncrossed.
isNice := proc(Ldir) local Delta, dir, ep, mp, path;
   Delta := [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]];
   ep := [0,0]; path := {ep};
   for dir in Ldir do
      mp := ep + Delta[dir];
      ep := mp + Delta[dir];
      path := {op(path), mp, ep};
   od;
   return evalb(nops(path)=2*nops(Ldir)+1);
end:
# Count only king tours which are nice, i.e. self-avoiding and uncrossed.
A272773 := proc(n) local count, T, p;
   count := 0:
   T := combinat[cartprod]([seq([$1..8], j=1..n)]):
   while not T[finished] do
      p := T[nextvalue]();
      if isNice(p) then count := count+1; fi;
   od:
   return count;
end: # Rainer Rosenthal, Jan 06 2019

mo = Most@Tuples[{-1, 1, 0}, 2]; a[0] = 1; a[tg_, p_: {{0, 0}}] := Block[{e, z = Last@p, w, mv = {}}, Do[w = {z+e, z+2*e}; If[Intersection[w, p] == {}, AppendTo[mv, w]], {e, mo}]; If[tg == 1, Length[mv], Sum[a[tg-1, Join[p, e]], {e, mv}]]]; a /@ Range[0, 7] (* Corrected following a suggestion by Rainer Rosenthal, Giovanni Resta, Jan 06 2019 *)

a(5)-a(7) corrected by Rainer Rosenthal, Jan 06 2019

a(8)-a(16) from Hugo Pfoertner, Jan 06 2019

A186864 Number of 5-step king's tours on an n X n board summed over all starting positions.

Original entry on oeis.org

0, 0, 1208, 6712, 17280, 32520, 52432, 77016, 106272, 140200, 178800, 222072, 270016, 322632, 379920, 441880, 508512, 579816, 655792, 736440, 821760, 911752, 1006416, 1105752, 1209760, 1318440, 1431792, 1549816, 1672512, 1799880, 1931920

Offset: 1

R. H. Hardin, Feb 27 2011

Row 5 of A186861.
From David A. Corneth, Sep 04 2023: (Start)
Proof of a(n) = 2336*n^2 - 10456*n + 11160 for n > 3.
For any walk we can find the surrounding rectangle it fits in.
For example, the walk
  0 1 2
  0 3 5
  0 4 0
has width 2 and height 3.
So it fits max(0, (5 - 2 + 1))*max(0, (5 - 3 + 1)) times in a 5 X 5 grid. This way we can set up a matrix m for all possible walks where element m(r, k) is the number of walks with dimensions (r, k).
That matrix is as follows:
  [0   0   0   0  2]
  [0   0 160 192 60]
  [0 160 568 312 72]
  [0 192 312 120 24]
  [2  60  72  24  4]
To find a(n) by iterating over this matrix we can compute Sum_{r=1..min(n, 5)} Sum_{k=1..min(n, 5)} m(r, k)*(n - r + 1)*(n - k + 1). This is the sum of 25 quadratics and gives the stated quadratic which completes the proof. (End)

			Some solutions for 3 X 3:
  0 5 0   0 1 2   3 1 0   3 2 1   0 1 2   0 1 2   0 5 0
  2 3 4   0 3 5   2 4 0   5 4 0   0 4 3   0 5 3   1 3 4
  1 0 0   0 4 0   5 0 0   0 0 0   0 5 0   0 0 4   2 0 0

David A. Corneth, Table of n, a(n) for n = 1..10000 (terms 1..32 from R. H. Hardin, terms 33..50 from J. Volkmar Schmidt)
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A186861, A272763.

LinearRecurrence[{3,-3,1},{0,0,1208,6712,17280,32520},50] (* Paolo Xausa, Oct 29 2023 *)

a(n) = if(n <= 3, [0, 0, 1608][n], 2336*n^2 - 10456*n + 11160) \\ David A. Corneth, Sep 04 2023

Empirical: a(n) = 2336*n^2 - 10456*n + 11160 = 8*(292*(n-1)*(n-4) + 153*n + 227) for n > 3. [Proved, see comments. - David A. Corneth, Sep 04 2023]
Conjectures from Colin Barker, Apr 19 2018: (Start)
G.f.: 8*x^3*(151 + 386*x + 96*x^2 - 49*x^3) / (1 - x)^3.
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 6. (End)
The above conjectures are true. - Stefano Spezia, Oct 28 2023

A376606 a(n) is the numerator of the expected number of moves to reach a position outside an nXn chessboard, starting in one of the corners, when performing a random walk with unit steps on the square lattice.

Original entry on oeis.org

1, 2, 11, 10, 99, 122, 619, 4374, 187389, 482698, 11031203, 33386106, 32723853563, 139832066, 150236161755, 633573154269934, 5755694771977, 189378719187729770, 509943025510535499, 6031948951257694364778, 1044408374351599765540157091, 27891966006517951087819226666

Offset: 1

Ruediger Jehn and Hugo Pfoertner, Oct 03 2024

The moves are that of chess rook with moves of unit length or of a chess king restricted to the Von Neumann 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, 2, 11/4, 10/3, 99/26, 122/29, 619/136, 4374/901, 187389/36562, 482698/89893, ...
Approximately 1, 2, 2.75, 3.333, 3.808, 4.207, 4.551, 4.855, 5.125, 5.370, 5.593, ...

Hugo Pfoertner, Table of n, a(n) for n = 1..45
Hugo Pfoertner, Plot of A376606(n)/A376607(n) vs n, using Plot 2.

A376607 are the corresponding denominators.
A376609 and A376610 are similar for a chess king visiting the Moore neighborhood.
A376736 and A376737 are similar for a chess knight.
Cf. A001263, A007764, A272763.

droprob(n,moves=[[1,0],[0,1],[0,-1],[-1,0]], nmoves=4) = {my(np=n^2+1, M=matrix(np), P=1/nmoves); for(t=1, nmoves, for( i=1, n, my(ti=i+moves[t][1]); for(j=1,n,my(tj=j+moves[t][2]); my(m=(i-1)*n+j); if(ti<1 || ti>n || tj<1 || tj>n, M[m,np]+=P, my(mt=(ti-1)*n+tj); M[m,mt]+=P)))); vecsum((1/(matid(np)-M))[,1])};
a376606(n) = numerator(droprob(n))

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

A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.

Original entry on oeis.org

1, 3, 15, 75, 391, 2065, 11091, 60215, 330003, 1820869, 10103153, 56313047, 315071801, 1768489771, 9953853677, 56158682949, 317505199769, 1798402412539

Offset: 0

Ricardo Bittencourt, Mar 10 2018

All terms are odd.

			For n=2, the a(2)=15 paths are:
.
.    0 . .     0 . .     0 . .     0 2 .     0 . .
.    |         |         |         |/         \
.    1 . .     1 . .     1-2 .     1 . .     2-1 .
.    |          \
.    2 . .     . 2 .     . . .     . . .     . . .
.
.    0 . .     0 . .     0 . .     0 . .     0 . 2
.     \         \         \         \         \ /
.    . 1 .     . 1 .     . 1 .     . 1-2     . 1 .
.     /          |          \
.    2 . .     . 2 .     . . 2     . . .     . . .
.
.    0 2 .     0-1 .     0-1 .     0-1 .     0-1-2
.     \|        /          |          \
.    . 1 .     2 . .     . 2 .     . . 2     . . .
.
.    . . .     . . .     . . .     . . .     . . .

Ricardo Bittencourt, C++ code, GitHubGist.
Ricardo Bittencourt, Go code, GitHubGist.
OEIS Wiki: Self-avoiding walks

A038373 is the same process, but using only horizontal and vertical moves.

Cf. A005773, A272469, A272763, A272773.

Go
```
(see GitHubGist link)
```

next[x_]:=Map[x + #&, Tuples[{-1, 0, 1}, 2]]
valid[s_]:=Select[next[s[[-1]]], 0<=#[[1]] && 0<=#[[2]] && FreeQ[s,#] &]
nextpath[p_]:=Outer[Append,{p},valid[p],1]
iterate[p_]:=Flatten[Map[nextpath, p], 2]
Table[Length[Nest[iterate, {{{0,0}}}, n-1]], {n,1,7}]

a(n) = A272469(n) + 2*A005773(n+1) - 1 for n > 0. - Andrey Zabolotskiy, Mar 12 2018

A344813 Square of the distance from the origin for a square lattice Moore neighborhood self-avoiding walk using the rules given in the Comments.

Original entry on oeis.org

0, 1, 5, 13, 25, 18, 32, 50, 41, 61, 85, 72, 98, 85, 61, 74, 100, 89, 65, 80, 58, 73, 97, 90, 116, 106, 117, 149, 130, 113, 145, 181, 162, 128, 145, 113, 130, 164, 149, 117, 136, 106, 125, 97, 73, 90, 68, 50, 36, 50, 37, 53, 73, 58, 80, 106, 89, 117, 100, 74, 52, 34, 20, 10, 17, 9, 17, 10, 4, 5

Offset: 1

Eric Angelini and Scott R. Shannon, May 29 2021

On a square lattice, where the walk can step to any of the eight unvisited nearest neighboring points (Moore neighborhood), start at the origin on the square numbered 1 and then step directly north to a square numbered 2. From then on sum the numbers in the last two visited squares, where each square is numbered with the next distinct integer after 2 as it is visited. If that sum is a prime number, the next step is to an unvisited square that is as far away from the origin as possible. If the sum is not prime then step to an unvisited square as close as possible to the origin. In either case if two squares exist that are the same distance from the origin then step to the square that is as far away from, if the sum is prime, or as close to, if the sum is composite, to the square with number 2. If these distances are the same, then step similarly to the square with number 3.

The sequence gives the square of the distance from the origin for the visited squares of this walk. The sequence is finite. After 128 steps, 129 visited squares, the walk ends as all eight neighboring squares have been visited.

			a(3) = 5. The second square has coordinates (0,1) and the sum of the first two numbers is 1 + 2 = 3, which is prime. Therefore, to move as far away from the origin as possible, a step to (1,2) is taken, which has a square distance of 5 units from the origin. Note that a step to (-1,2) could have also been taken and would lead to the same walk by symmetry.
a(6) = 18 as a(5) is at coordinates (3,4) and the sum of the last two square numbers is 4 + 5 = 9, which is composite. Therefore, to step to a square as close as possible to the origin, a step to (3,3) is taken, which has a square distance of 18 units from the origin.
a(9) = 41 as a(8) is at coordinates (5,5) and the sum of the last two square numbers is 7 + 8 = 15, which is composite. Two squares as close as possible to the origin are available, (4,5) and (5,4), both of which have a square distance from the origin of 41 units. Since (4,5) has a square distance of 32 units from the square numbered 2, and (5,4) has a square distance of 34 units from 2, the former is chosen.

Eric Angelini, A self-trapped sum?, personal blog "Cinquante signes", May 20, 2021.
Eric Angelini, A self-trapped sum?, personal blog "Cinquante signes", May 20, 2021. [Cached copy]
Scott R. Shannon, Image of the full walk. The colors are graduated across the spectrum to show the relative step order.

Cf. A272763, A272773, A000040, A002808.

cp's OEIS Frontend

A272773 Number of n-step self-avoiding nonintersecting walks on the square lattice with diagonals allowed (corresponds to using the Moore neighborhood).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Extensions

A186864 Number of 5-step king's tours on an n X n board summed over all starting positions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A376606 a(n) is the numerator of the expected number of moves to reach a position outside an nXn chessboard, starting in one of the corners, when performing a random walk with unit steps on the square lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Go

Mathematica

Formula

A344813 Square of the distance from the origin for a square lattice Moore neighborhood self-avoiding walk using the rules given in the Comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs