login
Running time of Takeuchi function.
2

%I #34 Nov 18 2023 03:09:40

%S 0,1,4,14,53,223,1034,5221,28437,165859,1029803,6772850,46983238,

%T 342509396,2615606677,20865444825,173446634597,1499111445237,

%U 13445550920288,124919896067530,1200320663197275,11910845573790488

%N Running time of Takeuchi function.

%D D. E. Knuth, personal communication.

%D V. Lifschitz, editor, Artificial intelligence and mathematical theory of computation. Papers in honor of John McCarthy. Academic Press, Inc., Boston, MA, 1991. See p. 215.

%D T. Prellberg, On the asymptotics of Takeuchi numbers, Symbolic computation, number theory, special functions, physics and combinatorics, Kluwer Acad. Publ., Dordrecht, 2001, pp. 231-242. MR 2002m:11016.

%H Vaclav Kotesovec, <a href="/A000651/b000651.txt">Table of n, a(n) for n = 0..570</a>

%H Paul Barry, <a href="http://arxiv.org/abs/1107.5490">Invariant number triangles, eigentriangles and Somos-4 sequences</a>, arXiv preprint arXiv:1107.5490 [math.CO], 2011.

%H T. Prellberg, <a href="http://algo.inria.fr/seminars/sem02-03/prellberg1-slides.ps">On the asymptotic analysis of a class of linear recurrences</a> (slides).

%H T. Prellberg, <a href="https://arxiv.org/abs/math/0005008">On the Asymptotics of Takeuchi Numbers</a>, arXiv:math/0005008 [math.CO], 2000.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TakeuchiNumber.html">Takeuchi Number</a>

%F G.f. A(z) satisfies A(z-z^2)/z - A(z) = 1/(1-z) + z/(1-z+z^2). (Prellberg).

%F Asymptotic growth: a(n) ~ C_T*B(n)*exp(1/2*W(n)^2), where B(n) are the Bell numbers, W(n) the Lambert W function and C_T = 2.2394331040...(Prellberg).

%t a[n_] := a[n] = If[n < 1, 0, Sum[ (2*k)!/k!/(k+1)!, {k, 1, n}] + Sum[ (2*Binomial[n+k-1, k] - Binomial[n+k, k])*a[n-1-k], {k, 0, n-2}]]; Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Mar 11 2013, after Pari *)

%o (PARI) a(n)=if(n<1,0,sum(k=1,n,(2*k)!/k!/(k+1)!)+sum(k=0,n-2,(2*binomial(n+k-1,k)-binomial(n+k,k))*a(n-1-k)))

%Y Cf. A143307.

%K nonn

%O 0,3

%A _N. J. A. Sloane_

%E Typo in formula corrected by _Vaclav Kotesovec_, Sep 16 2013