My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
December 14th, 2018, 08:02 AM   #1
Newbie
 
Oliver1978's Avatar
 
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 10:31 AM.
Oliver1978 is offline  
 
December 18th, 2018, 05:35 PM   #2
Senior Member
 
Joined: Aug 2008
From: Blacksburg VA USA

Posts: 354
Thanks: 7

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
billymac00 is offline  
December 19th, 2018, 06:37 AM   #3
Newbie
 
Oliver1978's Avatar
 
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?
Oliver1978 is offline  
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,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 04:46 AM.
Eucler is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 hyper-operators/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





Copyright © 2019 My Math Forum. All rights reserved.