A000651 Running time of Takeuchi function.

0, 1, 4, 14, 53, 223, 1034, 5221, 28437, 165859, 1029803, 6772850, 46983238, 342509396, 2615606677, 20865444825, 173446634597, 1499111445237, 13445550920288, 124919896067530, 1200320663197275, 11910845573790488

Offset

0,3

References

D. E. Knuth, personal communication.

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.

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.

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..570

Paul Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, arXiv preprint arXiv:1107.5490 [math.CO], 2011.

T. Prellberg, On the asymptotic analysis of a class of linear recurrences (slides).

T. Prellberg, On the Asymptotics of Takeuchi Numbers, arXiv:math/0005008 [math.CO], 2000.

Eric Weisstein's World of Mathematics, Takeuchi Number

Formula

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

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).

Mathematica

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 *)

Prog

(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)))

Crossrefs

Cf. A143307.

Sequence in context: A112872 A162482 A308555 * A192247 A118896 A145211

Adjacent sequences: A000648 A000649 A000650 * A000652 A000653 A000654

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Typo in formula corrected by Vaclav Kotesovec, Sep 16 2013

Status

approved