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

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:

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.

**.**__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))
```

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: