7

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?

Nathan BeDell
  • 3,145
  • 14
  • 23
  • 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
  • 3
    I think it would be better if you kept to the conventional [Knuth up-arrow notation](https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation) $\uparrow\uparrow$ for tetration. – r.e.s. Jun 20 '14 at 14:14

1 Answers1

2

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.

Nathan BeDell
  • 3,145
  • 14
  • 23
  • 2
    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 06:54