cp's OEIS Frontend

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

%I A300665 #44 Jul 06 2022 06:40:13
%S A300665 1,3,15,75,391,2065,11091,60215,330003,1820869,10103153,56313047,
%T A300665 315071801,1768489771,9953853677,56158682949,317505199769,
%U A300665 1798402412539
%N A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.
%C A300665 All terms are odd.
%H A300665 Ricardo Bittencourt, <a href="https://gist.github.com/ricbit/705f123cc4b0026e6c7835a908a444b9">C++ code</a>, GitHubGist.
%H A300665 Ricardo Bittencourt, <a href="https://gist.github.com/ricbit/d74de089bcdb3d0623bfd047b393ce31">Go code</a>, GitHubGist.
%H A300665 OEIS Wiki: <a href="https://oeis.org/wiki/Self-avoiding_walks">Self-avoiding walks</a>
%F A300665 a(n) = A272469(n) + 2*A005773(n+1) - 1 for n > 0. - _Andrey Zabolotskiy_, Mar 12 2018
%e A300665 For n=2, the a(2)=15 paths are:
%e A300665 .
%e A300665 .    0 . .     0 . .     0 . .     0 2 .     0 . .
%e A300665 .    |         |         |         |/         \
%e A300665 .    1 . .     1 . .     1-2 .     1 . .     2-1 .
%e A300665 .    |          \
%e A300665 .    2 . .     . 2 .     . . .     . . .     . . .
%e A300665 .
%e A300665 .    0 . .     0 . .     0 . .     0 . .     0 . 2
%e A300665 .     \         \         \         \         \ /
%e A300665 .    . 1 .     . 1 .     . 1 .     . 1-2     . 1 .
%e A300665 .     /          |          \
%e A300665 .    2 . .     . 2 .     . . 2     . . .     . . .
%e A300665 .
%e A300665 .    0 2 .     0-1 .     0-1 .     0-1 .     0-1-2
%e A300665 .     \|        /          |          \
%e A300665 .    . 1 .     2 . .     . 2 .     . . 2     . . .
%e A300665 .
%e A300665 .    . . .     . . .     . . .     . . .     . . .
%t A300665 next[x_]:=Map[x + #&, Tuples[{-1, 0, 1}, 2]]
%t A300665 valid[s_]:=Select[next[s[[-1]]], 0<=#[[1]] && 0<=#[[2]] && FreeQ[s,#] &]
%t A300665 nextpath[p_]:=Outer[Append,{p},valid[p],1]
%t A300665 iterate[p_]:=Flatten[Map[nextpath, p], 2]
%t A300665 Table[Length[Nest[iterate, {{{0,0}}}, n-1]], {n,1,7}]
%o A300665 (C++) (see GitHubGist link)
%o A300665 (Go) (see GitHubGist link)
%Y A300665 A038373 is the same process, but using only horizontal and vertical moves.
%Y A300665 Cf. A005773, A272469, A272763, A272773.
%K A300665 nonn,walk,more
%O A300665 0,2
%A A300665 _Ricardo Bittencourt_, Mar 10 2018