A074877 Number of function calls required to compute ack(3,n), where ack denotes the Ackermann function.

15, 106, 541, 2432, 10307, 42438, 172233, 693964, 2785999, 11164370, 44698325, 178875096, 715664091, 2862983902, 11452590817, 45811673828, 183249316583, 733002509034, 2932020521709, 11728103058160, 46912454175475, 187649900587766, 750599770123001, 3002399416036092

Offset

0,1

Comments

The Ackermann function is defined recursively for nonnegative integers m,n by: ack(0,n) = n + 1 if m=0; ack(m,0) = ack(m-1,1) if m>0 and n=0; ack(m,n) = ack(m-1,ack(m,n-1)) otherwise.

Links

Table of n, a(n) for n=0..23.

Gert Bultman, Ackermann function.

Y. Sundblad, The Ackermann function. A theoretical, computational and formula manipulative study, Nordisk Tidskr. Informationsbehandling (BIT) 11 (1971), 107-119.

Eric Weisstein's World of Mathematics, Ackermann function.

Wikipedia, Ackermann function.

Index entries for sequences related to Ackermann function

Index entries for linear recurrences with constant coefficients, signature (8,-21,22,-8).

Formula

G.f.: (15-14*x+8*x^2)/((4*x-1)*(2*x-1)*(x-1)^2); recurrence: a(n) = 8*a(n-1)-21*a(n-2)+22*a(n-3)-8*a(n-4); a(n) = 128/3*4^n-40*2^n+3*n+37/3 for n>=0. - Pab Ter (pabrlos(AT)yahoo.com), May 29 2004

a(n) ~ 128/3*4^n. [Charles R Greathouse IV, Dec 09 2011]

Mathematica

Table[128 / 3 4^n - 40 2^n + 3 n + 37 / 3, {n, 0, 30}] (* Vincenzo Librandi, Apr 19 2015 *)

Prog

(PARI) a(n)=128/3*4^n-40*2^n+3*n+37/3 \\ Charles R Greathouse IV, Dec 09 2011
(Magma) [128/3*4^n-40*2^n+3*n+37/3: n in [0..30]]; // Vincenzo Librandi, Apr 19 2015

Crossrefs

Two kinds of calls: A304370, A304371.

Sequence in context: A041426 A278781 A275644 * A293263 A202255 A243212

Adjacent sequences: A074874 A074875 A074876 * A074878 A074879 A074880

Keyword

nonn,easy

Author

Jeff Medha (medha_jeff(AT)yahoo.co.in), Sep 12 2002

Extensions

Edited by Pab Ter (pabrlos(AT)yahoo.com), May 29 2004

More terms from Vincenzo Librandi, Apr 19 2015

Status

approved