What's a general algorithm/technique to find the last digit of a nested exponential?

Question

So I'm working on this particular question at codewars, and asking this here because I've been trying to work it out for a day and a half now.
The purpose: To find the last digit of a nested exponent given as:$$a_0^{a_1^{a_2^{a_3^{.^{.^.}}}}}$$ Note that this is not infinite, just that any number of variables can be given,ie, there can be one or two or any number of exponents

These are a few things I've tried:
1.Looking for patterns: I noticed that if $a_1$'s last digit is 1,5 or 6, the answer is 1,5,6 respectively. Other observations include 4 ,9 having a cycle of 2 and 2,3,7,8 having a cycle of 4.
2. I've dabbled into modular arithmetic, spending hours trying to understand the use of Euler's Theorem and the Chinese remainder theorem in this problem.
After understanding them sufficiently, I have still not been able to come up with a satisfactory "general" form, and the variety of sources I've consulted have got me confused on the actual implementation of these algorithms here.

This seems doable but I am pretty young and have zero experience in number theory, and would honestly appreciate any help you guys could give me.

Answer 1

If the power tower contains a zero (but not two consecutive zeros, in which case we get trouble because $0^0$ is undefined), then you can remove all numbers upto the number before the first zero. Should this be the base, the result is $1$.

If the power tower does not contain a zero and has at least three entries, then the following algorithm does the job :

Calculation modulo $2$

• The power tower is even if and only if the base is even.

Calculation modulo $5$

• If the base if divisbly by $5$, the result is $0$: If not, replace the base by its residue mod $5$ , denote this value $b$ and continue.
• If the first exponent is even, then the result is $1$, unless the second exponent is $1$ and the first exponent is of the form $4k+2$. In this case, the result is $b^2$ mod $5$
• If the first exponent is odd, replace it by its residue mod $4$ and replace the second exponent by its residue mod $2$. Remove all other exponents and calculate the remaining power tower.

Finally, the chinese remainder theorem easily gives the residue mod $10$

Answer 2

The last (decimal) digit of a number is the number's residue modulo $10$, so the general kind of problem you need to solve is

Given a power tower $a_0^{a_1^{\vdots^{a_n}}}$ and a small modulus $m$, compute $$a_0^{a_1^{\vdots^{a_n}}} \bmod m$$

The first step is of course to rewrite this to $$(a_0\bmod m)^{a_1^{\vdots^{a_n}}} \bmod m$$ using general facts about modular arithmetic. Now in the particular case that $a_0$ is coprime to $m$, Euler's theorem allows us to rewrite this to $$ (a_0\bmod m)^{\bigl(a_1^{\vdots^{a_n}} \bmod \varphi(m)\bigr)} \bmod m$$ in which the exponent is now a simpler instance of the original problem -- simpler because the tower is one level shorter and $\varphi(m)$ is less than $m$ (unless $m=1$ in which case anything mod $m$ is $0$ anyway and you can throw the entire tower away).

Once you have reduced the exponent you can raise $a_0\bmod m$ to it by standard techniques such as exponentiation by squaring -- or just by winging it if $m$ is as small as 10 and you have 32-bit arithmetic.

If $a_0$ and $m$ are not coprime, then the slick theoretical approach is to factor $m$ and use the Chinese remainder theorem, but a kind of poor man's shortcut is this bastard offshot of Euler's theorem:

If $a$ and $m$ are arbitrary positive integers and $b\ge\varphi(m)$, then $$ a^b \equiv a^{\varphi(m)+(b\bmod\varphi(m))} \pmod m$$

So if you can just recognize whether or not the upper tower is large (which is easy), you can reduce the task to raising to a number that is not larger than $2\varphi(m)$.

Since your starting $m$ is $10$, you don't need any fancy machinery for computing $\varphi(m)$ -- just hardcode a table for $m$ up to $10$. (In fact the only $m$ you will need are $10,4,2,1$).

Answer 3

(This answer assumes all the $a_i$ are non-negative integers.)

Consider $t = a^{b^c}$ (where $c$ may be a power tower).

If $b^c = 0$, set $t = 1$. Otherwise, if $a = 0$, set $t = 0$. (Edited to swap the two cases handling zeroes.)

So now we know $a > 0$ and $b^c > 0$.

Otherwise, by the Chinese remainder theorem, it is enough to know the value of $t$ modulo $2$ and $5$ to recover the last decimal digit.

• If $a$ is even, $t$ is even (i.e. is congruent to $0$ modulo $2$).
• If $a$ is odd , $t$ is odd (i.e. is congruent to $1$ modulo $2$).

This is enough to tell us if $c$ is even or odd if $c$ is a power tower.

Now we just need to find $a^{b^c} \pmod{5}$. By Fermat's little theorem, $a^4 \cong 1 \pmod{5}$, so it is sufficient to know how $4$ divides into $b^c$, i.e., to know $q$ and $r$ in $b^c = 4q+r$, because then $t = a^{4q+r} = a^{4q} a^r = (a^4)^q a^r \cong 1^q a^r \cong a^r \pmod{5}$. In fact, we only need $r$, the remainder, so we only need to know $b^c \pmod{4}$. (We could use Euler's theorem here, but it will tell us exactly the same thing because $5$ is prime.)

If $c = 0$, $b^c \cong 1 \pmod{4}$, so $t \cong a^1 \cong a \pmod{5}$.

Otherwise, we use the useful facts: If $b$ is even, $b^2 \cong 0 \pmod{4}$ and if $b$ is odd, $b^2 \cong 1 \pmod{4}$. So we only need to know whether each of $b$ and $c$ is even or odd to determine $b^c \pmod{4}$.

• If $b$ and $c$ are even, $b^c \cong 0 \pmod{4}$. (Easy way to see: $(2x)^{2y} = 2^{2y}x^{2y} = 4^y x^{2y}$, so is a multiple of $4$. In fact, slight variations of this work for all four cases here.)
• If $b$ is even and $c$ is odd, $b^c \cong 2 \pmod{4}$.
• If $b$ is odd and $c$ is even, $b^c \cong 1 \pmod{4}$.
• If $b$ is odd and $c$ is odd, $b^c \cong b \pmod{4}$. If $b \cong 1 \pmod{4}$, this is $b^c \cong 1 \pmod{4}$ and if $b \cong 3 \pmod{4}$, this is $b^c \cong 3 \pmod{4}$.

So now we know $t \cong a^0, a^1, a^2, a^3 \pmod{5}$, depending on easily extracted properties of $b$ and $c$. So we calculate this power of $a$ and reduce modulo $5$.

Having found $t \pmod{2}$ and $t \pmod{5}$, we can use the Chinese remainder theorem to find $t \pmod{10}$, i.e. the last decimal digit of $t$. (Easy way: Suppose we have $3 \pmod{5}$, then the last digit is either $3$ or $8$. Did you want the even one or the odd one?)

---

Example computation:

$t_1 = 0^{0^{0^{0^{0^0}}}}$, so $a_1 = b_1 = 0, c_1 = 0^{0^{0^0}}$. To determine if $b_1^{c_1} = 0$, we must evaluate $c_1$.

$c_1 = 0^{0^{0^0}}$, so $a_2 = b_2 = 0, c_2 = 0^0$. To determine if $b_2^{c_2} = 0$, we must evaluate $c_2$.

$c_2 = 0^0$, so $a_3 = b_3 = 0, c_3 = \, $. Then $b_3^{c_3} = 0^{\,}$, so $c_2 = 1$.

Then $b_2^{c_2} = 0^1 = 0$, so $c_1 = 1$.

Then $b_1^{c_1} = 0^1 = 0$, so $t = 1$.