6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gottfried Helms Jun 10 '14 at 15:59
  • $\begingroup$ $ 3 \uparrow 4 = 3^{3^{3^3}} $ $\endgroup$ – Nathan BeDell Jun 10 '14 at 16:05
  • 1
    $\begingroup$ I think it would be better if you kept to the conventional Knuth up-arrow notation $\uparrow\uparrow$ for tetration. $\endgroup$ – r.e.s. Jun 20 '14 at 14:14
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Gottfried Helms May 29 '17 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.