I want to compute last few digts (as much as possible ) of the following number $$ N:=n^{n^{n^{\cdot^{\cdot^{\cdot^n}}}}}\!\!\!\hspace{5 mm}\mbox{ if there are $k$ many $n$'s in the expression and $n\in\mathbb{N}$ }$$ I have seen many particular cases of this problem. I think for odd $n$ the units digit is $n^3\mbox{ mod } 10 $ and for even $n$ the units digit is 6, for all $k\geq 3$ . How much can we say about the other digits ?

  • 3
    $\begingroup$ $3^{(3^3)} = 3^{27} \ne 3^9 = 3^{3 \times 3} = (3^3)^3$. The operation of raising to the power is not associative. $\endgroup$ – penartur Jul 3 '12 at 11:11
  • 3
    $\begingroup$ Whilst this is true, I think the usual convention is that the brackets start from the top. So $x^{y^z}$ becomes $x^{(y^z)}$ $\endgroup$ – Sam Jones Jul 3 '12 at 11:15
  • 9
    $\begingroup$ By $n^{n^{n^n}}$ I mean $n^{(n^{(n^n)})}$ and I think this is usually meant by what I wrote $\endgroup$ – pritam Jul 3 '12 at 11:16
  • 2
    $\begingroup$ You can write it using Knuth's up-arrow notation as $n\uparrow\uparrow k$, that way there's no ambiguity. ;) $\endgroup$ – tomasz Jul 3 '12 at 12:38
  • 1
    $\begingroup$ math.stackexchange.com/a/162608/26068 This may be helpful $\endgroup$ – Saurabh Jul 3 '12 at 13:03

Taking $n=7$ and looking for the last three digits for an example, note that $7^m \pmod {1000}$ is periodic with period $20$. You can check this easily with a spreadsheet. So now, we only need the tower above the first $7$ to $\pmod {20}$. That has period $4$, so we only need the tower above the first two $7$'s $\pmod 4$. That has period $2$, and the stack above the bottom three $7$'s is always odd. So a tower of $k\ 7$'s has last three digits the same as $7^{7^7}$ for $ k \ge 4$. The upper $7$ is $3 \pmod 4$, so $7^7 \equiv 3 \pmod {20}$, so $7^{7^7} \equiv 343 \pmod {1000}$, so any taller tower ends in $343$

  • $\begingroup$ I think if this is true for $n=7$ then it is also true for any $n$ with last three digits $007$ $\endgroup$ – pritam Jul 3 '12 at 16:15
  • $\begingroup$ @pritam: you are correct $\endgroup$ – Ross Millikan Jul 3 '12 at 16:17
  • $\begingroup$ Except that $7^7 \equiv 3 \mod 20$ and $7^{7^7} \equiv 343 \mod 1000$. $\endgroup$ – Robert Israel Jul 3 '12 at 18:03
  • 2
    $\begingroup$ @RobertIsrael: Thanks. Off-by-one error in my calcs. Fixed now. $\endgroup$ – Ross Millikan Jul 3 '12 at 18:07
  • $\begingroup$ ... and similarly $7 \uparrow \uparrow j \equiv 2343 \mod 10^4$ for $j \ge 3$, $172343 \mod 10^6$ for $j \ge 4$, $65172343 \mod 10^8$ for $j \ge 6$, ... $\endgroup$ – Robert Israel Jul 3 '12 at 18:46

Here's a little bit of computational knowledge...

If we want the first $d$ digits, we can calculate the result by modular arithmetic. In other words, modulo $10^d=2^d5^d$.

The more time-consuming portion is calculating the result modulo $5^m$. We can note that $$k^m \mod n \equiv k^{m \mod \phi(n)} \mod n$$ where $\phi(n)$ is Euler's Totient function.

We can apply this function recursively, i.e. $$m^m \mod n \equiv m^{m \mod \phi(n)} \mod n$$ $$m^{m^m} \mod n \equiv m^{\left(m^m \mod \phi(\phi(n))\right) \mod \phi(n)} \mod n$$ $$\dots$$ where $n=5^d$. Therefore, the most extensive operation is exponentiation modulo $n$. This can be done in $O(\log(n))$ operations via exponentiation by squaring or binary exponentiation. This operation is done at most $n$ times, so we get a conservative bound of $O(n \log(n))$ or, really, $O(5^d \log(5^d))$ operations.


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.