login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326955 Denominator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps. 3
1, 1, 8, 4, 512, 256, 16384, 8192, 2097152, 1048576, 16777216, 8388608, 4294967296, 2147483648, 68719476736, 34359738368, 35184372088832, 17592186044416, 281474976710656, 140737488355328, 18014398509481984 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

The starting square is always considered part of the walk.

LINKS

Table of n, a(n) for n=0..20.

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

EXAMPLE

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.

PROG

(Python)

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

CROSSREFS

See A326954 for numerators. Cf. A309221.

Sequence in context: A268482 A231234 A096687 * A199374 A289538 A154224

Adjacent sequences:  A326952 A326953 A326954 * A326956 A326957 A326958

KEYWORD

nonn,frac,walk

AUTHOR

Orson R. L. Peters, Aug 08 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 30 12:10 EDT 2020. Contains 333125 sequences. (Running on oeis4.)