
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
December 14th, 2018, 08:02 AM  #1 
Newbie Joined: Dec 2018 From: Germany Posts: 2 Thanks: 0  Ackermann function modulo calculations
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(n1, 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 skipjack; December 14th, 2018 at 10:31 AM. 
December 18th, 2018, 05:35 PM  #2 
Senior Member Joined: Aug 2008 From: Blacksburg VA USA Posts: 346 Thanks: 6 Math Focus: primes of course 
If you are not familiar with it, check out this link, it may give you some ideas. https://rosettacode.org/wiki/Ackermann_function 
December 19th, 2018, 06:37 AM  #3 
Newbie Joined: Dec 2018 From: Germany Posts: 2 Thanks: 0 
@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?

January 1st, 2019, 07:19 PM  #4 
Newbie Joined: Dec 2018 From: Euclidean Plane Posts: 7 Thanks: 3 
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,n1)) \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 skipjack; January 2nd, 2019 at 04:46 AM. 

Tags 
ackermann, calculations, function, modulo 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Ackermann function and primitive recursive functions  safyras  Linear Algebra  4  May 11th, 2014 11:59 AM 
is modulo operation a bijective function?  mathisdrama  Number Theory  0  February 13th, 2012 11:13 AM 
Ackermann's function A (2,2)  mathproblems  Applied Math  0  December 4th, 2011 10:18 AM 
solution to complex hyperoperators/Ackermann function  jamesuminator  Number Theory  5  June 25th, 2011 12:16 PM 
Ackermann's Function  aikiart  Computer Science  6  August 26th, 2010 11:50 AM 