cp's OEIS Frontend

A210735 Number of Dyck n-paths all of whose ascents and descents have prime lengths.

%I A210735 #17 Mar 24 2017 03:48:19
%S A210735 1,0,1,1,1,4,2,10,10,22,46,64,167,245,560,1035,1978,4210,7715,16497,
%T A210735 31929,65216,133295,266244,553750,1116404,2308931,4738660,9742795,
%U A210735 20204902,41622910,86539105,179358694,373018581,777157221,1618773690,3382590684,7065505631
%N A210735 Number of Dyck n-paths all of whose ascents and descents have prime lengths.
%H A210735 Alois P. Heinz, <a href="/A210735/b210735.txt">Table of n, a(n) for n = 0..900</a>
%F A210735 a(n) ~ c * d^n / n^(3/2), where d = 2.1792514215908330337..., c = 0.4751731999905254789... . - _Vaclav Kotesovec_, Sep 02 2014
%e A210735 a(0) = 1: the empty path.
%e A210735 a(1) = 0.
%e A210735 a(2) = 1: UUDD.
%e A210735 a(3) = 1: UUUDDD.
%e A210735 a(4) = 1: UUDDUUDD.
%e A210735 a(5) = 4: UUDDUUUDDD, UUUDDDUUDD, UUUDDUUDDD, UUUUUDDDDD.
%e A210735 a(6) = 2: UUDDUUDDUUDD, UUUDDDUUUDDD.
%e A210735 a(7) = 10: UUDDUUDDUUUDDD, UUDDUUUDDDUUDD, UUDDUUUDDUUDDD, UUDDUUUUUDDDDD, UUUDDDUUDDUUDD, UUUDDUUDDDUUDD, UUUDDUUDDUUDDD, UUUUUDDDDDUUDD, UUUUUDDUUDDDDD, UUUUUUUDDDDDDD.
%e A210735 a(8) = 10: UUDDUUDDUUDDUUDD, UUDDUUUDDDUUUDDD, UUUDDDUUDDUUUDDD, UUUDDDUUUDDDUUDD, UUUDDDUUUDDUUDDD, UUUDDDUUUUUDDDDD, UUUDDUUDDDUUUDDD, UUUDDUUUDDDUUDDD, UUUUUDDDDDUUUDDD, UUUUUDDDUUUDDDDD.
%p A210735 with(numtheory):
%p A210735 b:= proc(x, y, u) option remember;
%p A210735       `if`(x<0 or y<x, 0, `if`(x=0 and y=0, 1, `if`(u,
%p A210735        add(b(x-ithprime(t), y, false), t=1..pi(x)),
%p A210735        add(b(x, y-ithprime(t), true ), t=1..pi(y)))))
%p A210735     end:
%p A210735 a:= n-> b(n$2, true):
%p A210735 seq(a(n), n=0..40);
%t A210735 b[x_, y_, u_] := b[x, y, u] = If[x<0 || y<x, 0, If[x==0 && y==0, 1, If[u, Sum[b[x-Prime[t], y, False], {t, 1, PrimePi[x]}], Sum[b[x, y-Prime[t], True], {t, 1, PrimePi[y]}]]]];
%t A210735 a[n_] := b[n, n, True];
%t A210735 Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Mar 24 2017, translated from Maple *)
%Y A210735 Cf. A210737.
%K A210735 nonn
%O A210735 0,6
%A A210735 _Alois P. Heinz_, May 10 2012