cp's OEIS Frontend

A308087 Number of lattice paths from (0,0) to (n,n) using Euclid's orchard as a step-set.

%I A308087 #31 Feb 29 2020 03:35:59
%S A308087 1,1,1,3,13,45,153,515,1767,6167,21697,76661,271973,968561,3460677,
%T A308087 12399661,44534647,160285049,577949447,2087375443,7550053527,
%U A308087 27344761057,99155777619,359943568005,1307923066305,4756914915657,17315390737219,63077564876055
%N A308087 Number of lattice paths from (0,0) to (n,n) using Euclid's orchard as a step-set.
%H A308087 Alois P. Heinz, <a href="/A308087/b308087.txt">Table of n, a(n) for n = 0..575</a>
%H A308087 J. East and N. C. Ham, <a href="https://arxiv.org/abs/1811.05735">Lattice paths and submonoids of Z^2</a>, arXiv:1811.05735 [math.CO], 2018.
%H A308087 N. C. Ham, <a href="https://gitlab.com/n-ham-paper-files/lattice-path-algorithms">Implementation</a> of algorithms 1-3 from J. East and N. C. Ham reference above.
%H A308087 Wikipedia, <a href="https://en.wikipedia.org/wiki/Euclid&#39;s_orchard">Euclid's orchard</a>
%F A308087 a(n) mod 2 = 1. - _Alois P. Heinz_, May 13 2019
%F A308087 a(n) ~ c * d^n / sqrt(n), where d = 3.7137893481485186502229788321701955452444... and c = 0.133597878112414800677299372849715598093... - _Vaclav Kotesovec_, May 24 2019
%p A308087 b:= proc(x, y) option remember; `if`(y=0, 1, add(add(`if`(1=
%p A308087       igcd(h, v), b(sort([x-h, y-v])[]), 0), v=1..y), h=1..x))
%p A308087     end:
%p A308087 a:= n-> b(n$2):
%p A308087 seq(a(n), n=0..30);  # _Alois P. Heinz_, May 12 2019
%t A308087 b[x_, y_] := b[x, y] = If[y == 0, 1, Sum[Sum[If[1 == GCD[h, v], b @@ Sort[{x - h, y - v}], 0], {v, 1, y}], {h, 1, x}]];
%t A308087 a[n_] := b[n, n];
%t A308087 a /@ Range[0, 30] (* _Jean-François Alcover_, Feb 29 2020, after _Alois P. Heinz_ *)
%Y A308087 Cf. A001764, A005043, A005165, A035343, A067955, A097609, A308112, A308113.
%K A308087 nonn,walk
%O A308087 0,4
%A A308087 _Nicholas Ham_, May 11 2019
%E A308087 a(16)-a(27) from _Alois P. Heinz_, May 12 2019