2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You only need to consider the first three numbers in the power tower for modulo-$5$-calculation. Modulo $2$, you only need the base. $\endgroup$ – Peter Mar 29 '18 at 15:05
  • $\begingroup$ You basically need to find the (eventual) period of $a^n \bmod m$ as a function of $n$. This should reduce the problem to determining the eventual periodic behavior of the function and calculating $a^n \bmod m$ where $n\lt m$, which could be done via fast modular exponentiation. There could be further simplifications in this particular case, though. $\endgroup$ – Kitegi Mar 29 '18 at 15:37
  • $\begingroup$ Are the $a_i$ integers, non-negative integers, positive integers, something else? $\endgroup$ – Eric Towers Mar 29 '18 at 15:39
  • $\begingroup$ @EricTowers They're positive integers(including zero) $\endgroup$ – Rohan Gautam Mar 29 '18 at 17:26
  • $\begingroup$ See also: Last digit large number $\endgroup$ – Simply Beautiful Art Aug 12 '18 at 4:08
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ What about $7^{{6}^{21}}$ ? According to your steps, the two equations we get are 1(mod 2) and 4(mod 5). Using chinese remainder theorem, we get the answer as $9$ , however according to wolframalpha.com/input/?i=(7%5E(6%5E(21)))+mod+10 , the answer is 1 $\endgroup$ – Rohan Gautam Mar 30 '18 at 5:01
  • $\begingroup$ @RohanGautam True, $6^{21}$ is divisble by $4$, hence the result is $1$. I edited my answer. $\endgroup$ – Peter Mar 30 '18 at 7:00
  • $\begingroup$ The question assumes $0^0=1$ and $0^n=0$ (where n is a natural number, not zero). Can you help me out when that is the case? This is kinda confusing and your answer is one of the clearer ones so thanks a lot again $\endgroup$ – Rohan Gautam Apr 7 '18 at 17:32
  • $\begingroup$ @RohanGautam Additionaly using $a^0=1$ for $a\ne 0$ should do the job, or do you still have a case that it is not working ? $\endgroup$ – Peter Apr 7 '18 at 20:37
  • $\begingroup$ There are some cases where the exponent does not depend on the first 3 exponents alone. Like $0^{0^{0^{0}}}=1$ and $0^{0^{0^{0^{0}}}}=0$ That's where I'm stuck :/ $\endgroup$ – Rohan Gautam Apr 8 '18 at 17:56
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hey, thanks for the answer! The question assumes $0^0=1$ and $0^n=0$ (where n is a natural number, not zero). Can you help me out if this is the case? $\endgroup$ – Rohan Gautam Apr 7 '18 at 12:32
  • $\begingroup$ This is perfect if there are no zeroes in the tower, but the test cases have them and I'm stuck there :/ Thanks for your help! $\endgroup$ – Rohan Gautam Apr 7 '18 at 12:33
  • $\begingroup$ So ... swap the "If $a = 0$ ..." and the "Otherwise, ..." lines. $\endgroup$ – Eric Towers Apr 7 '18 at 16:31
  • $\begingroup$ Can you check out the comment thread in @Peter's answer? I'm hella stuck $\endgroup$ – Rohan Gautam Apr 23 '18 at 19:30
  • $\begingroup$ @RohanGautam : I've swapped the two lines I said to swap and these seem to do exactly what was advertised... Example included. $\endgroup$ – Eric Towers Apr 23 '18 at 22:16
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.