Ackermann function modulo calculations

Dec 2018
2
0
Germany
There's a programming puzzle at Programming Praxis in which one is to calculate values of the Ackermann function A(m, n). One comment was particularly helpful, you can see it here.
The function values of A(m, n) are known to get gigantic for m >= 4. Therefore I'd like to approach it with modulo operations. With an additional function "tetration" the code in Python looks like this:

Code:
def tetration(a, b, mod):
    ''
    t0 = 1

    while b > 0:
        t0 = pow(a, t0, mod)
        b -= 1

    return t0

def hyper(n, a, b, mod):
    ''
    if n == 0:
        return (b + 1) % mod
    if n == 1:
        return (a + b) % mod
    if n == 2:
        return (a * b) % mod
    if n == 3:
        return pow(a, b, mod)
    if n == 4:
        return tetration(a, b, mod)

    if b == 0:
        return 1

    x = a
    for _ in range(b - 1):
        x = hyper(n-1, a, x, mod)

    return x % mod

def ackermann(m, n, mod):
    ''
    return hyper(m, 2, n + 3, mod) - (3 % mod)

if __name__ == "__main__":
    ''
    print (ackermann(4, 2, 10**9 + 7))
So far, so good. A call to ackermann(4, 2, 10**9 + 7) gives 973586823 as the result. With values of m >= 5 the above code takes an awful lot of time. ackermann(5, 2, 10**9 + 7) finishes in approx. 26 minutes. Calls with m >= 6 are practically a neverending story.

Now, here's my question: Is there some (mathematical) way to considerably speed things up for values of m >= 5? The above code works well in terms of runtime for small moduli, but as they get bigger runtime increases unbearably.

Already thanks for having a look and helping. :)
 
Last edited by a moderator:
Dec 2018
2
0
Germany
@billymac00.... I had already tried that link, but didn't find anything which might point me in the right direction. Perhaps you have an idea where to look closer?
 
Dec 2018
7
3
Euclidean Plane
As indicated in your code, the Ackermann function is basically a power tower of twos when m >= 4:

\(\displaystyle
\begin{align*}
A(4,0) + 3 &= 2^{2^2}\\
A(4, 1) + 3 &= 2^{2^{2^2}}\\
A(4, 2) + 3 &= 2^{2^{2^{2^2}}}\\
\end{align*}
\)

and so forth. Now, I don't know how much number theory you know, but for a given modulus M, power towers will "stabilize" pretty quickly mod M. Here's an example of what I mean for M=19:

\(\displaystyle
\begin{align*}
2 \equiv 2 \text{ (mod }19\text{)}&\\
2^2 \equiv 4 \text{ (mod }19\text{)}&\\
A(4,0) + 3 = 2^{2^2} \equiv 16 \text{ (mod }19\text{)}&\\
A(4, 1) + 3 = 2^{2^{2^2}} \equiv 5 \text{ (mod }19\text{)}&\\
A(4, 2) + 3 = 2^{2^{2^{2^2}}} \equiv 5 \text{ (mod }19\text{)}&\\
A(4, 3) + 3 = 2^{2^{2^{2^{2^2}}}} \equiv 5 \text{ (mod }19\text{)}&
\end{align*}
\)

and in fact any power tower of twos with more than 3 twos will be congruent to 5 modulo 19. Proving this fact uses Euler's Theorem repeatedly, one version of which can be stated as follows:

If $a$ is relatively prime to $M$, then
$$a^x \equiv a^y \;\text{ mod }M \qquad \text{ if } \qquad x \equiv y \;\text{ mod }\phi(M)$$
where $\phi(M)$ is the Euler totient function. (I won't go into the details now since I'm not sure how much you already know, but I can provide further details if you like.)

For your modulus, the power tower stabilizes after only 7 twos:

For any n >= 4,
$$A(4, n) \equiv A(4, 4) = 2^{2^{2^{2^{2^{2^2}}}}}-3 \equiv 661944223 \;\;\text{(mod } 10^9 + 7 \text{)}.$$

From here you can calculate all of the rest of the values of the Ackermann function modulo your prime:

$$A(5, 0) \equiv A(4, 1) = 2^{2^{2^2}}-3 \equiv 65540\;\;\text{(mod } 10^9 + 7 \text{)}$$
and everything stabilizes after that point:
For all n>0,
$$A(5, n) = A(4, A(5,n-1)) \equiv A(4,4) \equiv 661944223 \;\;\text{(mod } 10^9 + 7 \text{)},$$ and similarly for all m > 5
$$A(m, n) \equiv A(4,4) \equiv 661944223 \;\;\text{(mod } 10^9 + 7 \text{)}.$$
 
Last edited by a moderator: