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

9, 58, 283, 1244, 5213, 21342, 86367, 347488, 1394017, 5584226, 22353251, 89445732, 357848421, 1431524710, 5726360935, 22905967976, 91624920425, 366501778794, 1466011309419, 5864053626220, 23456231282029, 93824958682478, 375299901838703, 1501199741572464

Offset: 0

Author

Olivier Gérard, May 11 2018

Keywords

• nonn
• easy

Comments

The distinction between different kinds of recursive calls is based on a naive implementation of the Ackermann function in C.

int ack(int m, int n)

{

// Final result

....if (m==0) return n + 1;

.

// Recursive calls of the first kind:

....if (n==0) return ack(m - 1, 1);

.

// Recursive calls of the second kind:

....return ack(m - 1, ack(m, n - 1));

}

Links

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

Crossrefs

Cf. A036563, A074877, A304371.

Formula

G.f.: (8*x^2-14*x+9)/((4*x-1)*(2*x-1)*(x-1)^2). - Alois P. Heinz, May 12 2018