Hyperexponentiation

The hyperexponentiation or tetration of a number $a$ by a positive integer $b$, denoted by $a\mathbin{\uparrow \uparrow}b$ or $^b a$, is recursively defined by:
$a \mathbin{\uparrow \uparrow} 1 = a$,
$a \mathbin{\uparrow \uparrow} (k+1) = a^{(a \mathbin{\uparrow \uparrow} k)}$.

Thus we have e.g. $3 \mathbin{\uparrow \uparrow} 2 = 3^3 = 27$, hence $3 \mathbin{\uparrow \uparrow} 3 = 3^{27} = 7625597484987$ and $3 \mathbin{\uparrow \uparrow} 4$ is roughly $10^{3.6383346400240996 \cdot 10^{12}}$.
Find the last $8$ digits of $1777 \mathbin{\uparrow \uparrow} 1855$.

Finding the exact value of $1777 \mathbin{\uparrow \uparrow} 1855$ obviously isn’t practical for these sorts of problems. However, we can use the concept of Euler’s totient theorem to simplify the problem.

Euler’s totient theorem states that if $a$ and $n$ are coprime, then $a^{\phi(n)} \equiv 1 \mod n$ where $\phi(n)$ is the Euler’s totient function, which represents the count of integers from $1$ to $n$ that are coprime with $n$.

When we need to find the last $8$ digits, we are asking for the remainder when the number $1777 \mathbin{\uparrow \uparrow} 1855$ is divided by $10^8$. So we can apply Euler’s theorem with $n = 10^8$.

Let’s suppose we set $b = 1777 \mathbin{\uparrow \uparrow} 1854$ and we want to find $a^b \mod 10^8$ with $a = 1777$ and $b$ being a potentially large integer.

We need to find the remainder of $b$ if divided by $\phi(10^8)$ which is $4 \times 10^6$. This is because while $a^{\phi(n)} \equiv 1 \mod n$, we also have $a^b \equiv a^{b\mod\phi(n)} \mod n$ and hence we only really need to consider $b\mod\phi(n) = b\mod 4 \times 10^6$ rather than $b$ itself.

Observe that $1777 \mathbin{\uparrow \uparrow} 1855$ and $1777 \mathbin{\uparrow \uparrow} 1854$ only differ at the highest level – the rest of the sequence is identical. This shows a pattern of $a^{n}$ for integers $n$ where $n < 4 \times 10^6$ is relatively small. So while $b = 1777 \mathbin{\uparrow \uparrow} 1854$ is extremely large, $b\mod 4 \times 10^6$ will be significantly smaller. Actually, we only need to calculate the sequence correctly upto the point where our power becomes $>= 4 \times 10^6$ as beyond that point repeating the cycle won’t change the exponent mod $4 \times 10^6$.

Applying these simplifications to the computation makes it possible to compute the problem easily with a computer program, yielding the result as $48168996$.

More Answers: