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,1

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

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

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

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

Mathematica

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

Crossrefs

Cf. A036563, A074877, A304370.

Sequence in context: A362430 A352303 A344121 * A049281 A354894 A219073

Adjacent sequences: A304368 A304369 A304370 * A304372 A304373 A304374

Keyword

nonn,easy

Author

Olivier Gérard, May 11 2018

Status

approved