|
%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
|
