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.
Best Answer
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
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:
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$).