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

%I #22 Sep 08 2022 08:45:07

%S 15,106,541,2432,10307,42438,172233,693964,2785999,11164370,44698325,

%T 178875096,715664091,2862983902,11452590817,45811673828,183249316583,

%U 733002509034,2932020521709,11728103058160,46912454175475,187649900587766,750599770123001,3002399416036092

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

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

%H Gert Bultman, <a href="http://hosting.xi-alles.nl/GertBultman/CS/recursion_ackermann.html">Ackermann function</a>.

%H Y. Sundblad, <a href="http://dx.doi.org/10.1007/BF01935330">The Ackermann function. A theoretical, computational and formula manipulative study</a>, Nordisk Tidskr. Informationsbehandling (BIT) 11 (1971), 107-119.

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

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Ackermann_function">Ackermann function</a>.

%H <a href="/index/Ab#Ackermann">Index entries for sequences related to Ackermann function</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (8,-21,22,-8).

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

%F a(n) ~ 128/3*4^n. [_Charles R Greathouse IV_, Dec 09 2011]

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

%o (PARI) a(n)=128/3*4^n-40*2^n+3*n+37/3 \\ _Charles R Greathouse IV_, Dec 09 2011

%o (Magma) [128/3*4^n-40*2^n+3*n+37/3: n in [0..30]]; // _Vincenzo Librandi_, Apr 19 2015

%Y Two kinds of calls: A304370, A304371.

%K nonn,easy

%O 0,1

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

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

%E More terms from _Vincenzo Librandi_, Apr 19 2015