My Math Forum Ackermann function modulo calculations

 Number Theory Number Theory Math Forum

 December 14th, 2018, 09: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(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 skipjack; December 14th, 2018 at 11:31 AM.
 December 18th, 2018, 06:35 PM #2 Senior Member   Joined: Aug 2008 From: Blacksburg VA USA Posts: 343 Thanks: 5 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, 07: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, 08: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,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 skipjack; January 2nd, 2019 at 05:46 AM.

 Tags ackermann, calculations, function, modulo

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post safyras Linear Algebra 4 May 11th, 2014 12:59 PM mathisdrama Number Theory 0 February 13th, 2012 12:13 PM mathproblems Applied Math 0 December 4th, 2011 11:18 AM jamesuminator Number Theory 5 June 25th, 2011 01:16 PM aikiart Computer Science 6 August 26th, 2010 12:50 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top