# Efficient algorithm for calculating the tetration of two numbers mod n?

I'm trying to study the algebraic properties of the magma created by defining the binary operation $x*y$ to be:

$x*y = (x \uparrow y) \bmod n$

where $\uparrow$ is the symbol for tetration.

Doing so, the hardest commutation necessary for this kind of magma of order n is: $(n-1) \uparrow (n-1) \bmod n$.

Using the standard algorithms for tetration and the modulus, this computation was instantaneous up to the magma of order 4. For the magma of order 5 however, with the computation $4 \uparrow 4 \bmod 5$, I could not compute it after 2+ hours. Is this computation even tractable for a core i7 laptop? (I'm using a library that allows for arbitrarily large integers) Is there a better way to do this computation than with a standard (brute force) calculation?

• is in $x \uparrow y$, for example $3 \uparrow 4$, meant $3^{3^{3^{3}}}$ or $4^{4^{4}}$ ? After that, exponentiation modulo some $n$ is cyclic to a cyclelength(order) smaller than n and so the expression in the exponent can be reduced level by level. – Gottfried Helms Jun 10 '14 at 15:59
• $3 \uparrow 4 = 3^{3^{3^3}}$ – Nathan BeDell Jun 10 '14 at 16:05
• I think it would be better if you kept to the conventional Knuth up-arrow notation $\uparrow\uparrow$ for tetration. – r.e.s. Jun 20 '14 at 14:14

Yes, simply iteratively reduce the exponents mod $n$ from right to left. e.x. $4^{4^{4^4}} (mod \; 5) = 4^{4^{256}} \; (mod \; 5) = 4^{4^1} \; (mod \; 5) = 256 \; (mod \; 5) = 1 \; (mod \; 5)$. This should be workably efficient for small numbers.
• One can have it even shorter, since $4^k \equiv 4^{k \mod 2} \pmod 5$. Then $4^{4^{4^4}} \equiv 4^{(4^{4^4}) \mod 2} \equiv 4^0 \equiv 1 \pmod 5$ . For other cases the move of the modular computation into the exponent can be taken iteratively even farther. – Gottfried Helms May 29 '17 at 6:54