A309221 -id:A309221 - cp's OEIS frontend

A326954 Numerator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps.

1, 2, 23, 15, 2355, 1395, 102971, 58331, 16664147, 9197779, 160882675, 87300443, 48181451689, 25832538281, 881993826001, 468673213505, 508090131646771, 268129446332211, 4514206380211785, 2369170809554097, 317528931045821675

Offset: 0

Orson R. L. Peters, Aug 08 2019

The starting square is always considered part of the walk.

			a(0) = 1 (from 1/1), we count the starting square.
a(1) = 2 (from 2/1), each possible first step is unique.
a(2) = 23 (from 23/8), as for each possible first step 1/8th of the second steps go back to a previous square, thus the expected distinct squares visited is 2 + 7/8 = 23/8.

Math StackExchange, Relatively efficient program to compute a(n) for larger n.

See A326955 for denominators. Cf. A309221.

from itertools import product
from fractions import Fraction
def walk(steps):
    s = [(0, 0)]
    for dx, dy in steps:
        s.append((s[-1][0] + dx, s[-1][1] + dy))
    return s
moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
         (2, 1), (2, -1), (-2, 1), (-2, -1)]
A326954 = lambda n: Fraction(
        sum(len(set(walk(steps)))
            for steps in product(moves, repeat=n)),
        8**n
    ).numerator

A326955 Denominator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps.

Original entry on oeis.org

1, 1, 8, 4, 512, 256, 16384, 8192, 2097152, 1048576, 16777216, 8388608, 4294967296, 2147483648, 68719476736, 34359738368, 35184372088832, 17592186044416, 281474976710656, 140737488355328, 18014398509481984

Offset: 0

Orson R. L. Peters, Aug 08 2019

The starting square is always considered part of the walk.

			a(0) = 1 (from 1/1), we count the starting square.
a(1) = 1 (from 2/1), each possible first step is unique.
a(2) = 8 (from 23/8), as for each possible first step 1/8th of the second steps go back to a previous square, thus the expected distinct squares visited is 2 + 7/8 = 23/8.

Math StackExchange, Relatively efficient program to compute a(n) for larger n.

See A326954 for numerators. Cf. A309221.

from itertools import product
from fractions import Fraction
def walk(steps):
    s = [(0, 0)]
    for dx, dy in steps:
        s.append((s[-1][0] + dx, s[-1][1] + dy))
    return s
moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
         (2, 1), (2, -1), (-2, 1), (-2, -1)]
A326955 = lambda n: Fraction(
        sum(len(set(walk(steps)))
            for steps in product(moves, repeat=n)),
        8**n
    ).denominator

cp's OEIS Frontend

A326954 Numerator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python