The inverse Ackermann function is defined as A1 m n minjAj

The inverse Ackermann function is defined as A^-1 (m, n) = min{j|A(j, [m/n]) greaterthanorequalto log n). A^-1(n, n) = min{j|A(j, 1) greaterthanorequalto log n}. Find numerical values for A^-1 (n, n) where n = 1..2^65533.

Solution

Inverse Ackermann Function

Because A(0,1) = 2, A(1,1) = 3, A(2,1) = 5, A(3,1) = 13, A(4,1) = 65533

the values of a(n) is as follows:

When n = 1 to 4: a(n) = 0 ,

When n = 5 to 8 : a(n) = 1 ,

When n = 9 to 32: a(n) = 2 ,

When n = 33 to 213: a(n) = 3 ,

When n = 2¹³+1 to 265533:a(n) = 4

Since 2⁶⁵⁵³³ >> 10⁸⁰, for all n that we concern,

a(n) £4 similarly, for all m, n that we concern,

if m ³n, a(m,n) £4

if m <n, a(m,n) £5