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

5, 47, 257, 1187, 5093, 21095, 85865, 346475, 1391981, 5580143, 22345073, 89429363, 357815669, 1431459191, 5726229881, 22905705851, 91624396157, 366500730239, 1466009212289, 5864049431939, 23456222893445, 93824941905287, 375299868284297, 1501199674463627

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, A304370.

Programs

Mathematica

LinearRecurrence[{8,-21,22,-8},{5,47,257,1187},30] (* Harvey P. Dale, Oct 22 2019 *)

Formula

A304370(n) + a(n) + 1 = A074877(n).

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