|
%I #11 Aug 28 2019 18:28:45
%S 1,1,8,4,512,256,16384,8192,2097152,1048576,16777216,8388608,
%T 4294967296,2147483648,68719476736,34359738368,35184372088832,
%U 17592186044416,281474976710656,140737488355328,18014398509481984
%N Denominator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps.
%C The starting square is always considered part of the walk.
%H Math StackExchange, <a href="https://math.stackexchange.com/a/3312917/5558">Relatively efficient program to compute a(n) for larger n</a>.
%e a(0) = 1 (from 1/1), we count the starting square.
%e a(1) = 1 (from 2/1), each possible first step is unique.
%e 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.
%o (Python)
%o from itertools import product
%o from fractions import Fraction
%o def walk(steps):
%o s = [(0, 0)]
%o for dx, dy in steps:
%o s.append((s[-1][0] + dx, s[-1][1] + dy))
%o return s
%o moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
%o (2, 1), (2, -1), (-2, 1), (-2, -1)]
%o A326955 = lambda n: Fraction(
%o sum(len(set(walk(steps)))
%o for steps in product(moves, repeat=n)),
%o 8**n
%o ).denominator
%Y See A326954 for numerators. Cf. A309221.
%K nonn,frac,walk
%O 0,3
%A _Orson R. L. Peters_, Aug 08 2019
|
