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

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$).

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$

(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$.