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

Author

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

Keywords

• nonn
• easy

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

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

Crossrefs

Two kinds of calls: A304370, A304371.

Programs

Magma

[128/3*4^n-40*2^n+3*n+37/3: n in [0..30]]; // Vincenzo Librandi, Apr 19 2015

Mathematica

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

PARI

a(n)=128/3*4^n-40*2^n+3*n+37/3 \\ Charles R Greathouse IV, Dec 09 2011

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]

Extensions

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

More terms from Vincenzo Librandi, Apr 19 2015