A383236 The least number of applications of Ackermann-Péter functions to reach n, starting from 0.

1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 5, 6, 7, 8, 8, 9, 9, 10, 9, 10, 10, 11, 10, 11, 11, 12, 6, 7, 8, 9, 10, 11, 11, 12, 11, 12, 12, 13, 12, 13, 13, 14, 12, 13, 13, 14, 13, 14, 14, 15, 13, 14, 14, 15, 14, 15, 15, 16, 7, 8, 9, 10

Offset

1,2

Comments

The Ackermann-Péter function is A(k,m) = A143796(k,m).

n >= 1 is reached by finding some n = A(k,m) with k and m each either 0 or further nested application(s) of A.

This sequence is slow-growing.

Links

Hendrik Ballhausen, Table of n, a(n) for n = 1..2048

Rózsa Péter, Konstruktion nichtrekursiver Funktionen, Mathematische Annalen, 111 (1935), 42-60.

Wikipedia, Ackermann function

Formula

a(n) = min_{k,m: A(k,m)=n} a(k) + a(m) + 1

Example

For n=65533, n = A(5,0) = A(A(2,1),0) = A(A(A(0,1),A(0,0)),0) = A(A(A(0,A(0,0)),A(0,0)),0) which is a(65533) = 5 applications of A, and this is the fewest possible.

Crossrefs

Cf. A143796 (Ackermann-Péter function).

Cf. A368423 (with Wainer hierarchy).

Sequence in context: A047741 A047784 A047742 * A302778 A203967 A365398

Adjacent sequences: A383233 A383234 A383235 * A383237 A383238 A383239

Keyword

nonn,look

Author

Hendrik Ballhausen, Apr 20 2025

Status

approved