1
$\begingroup$

I came across this challenge.

Find the last ten (least significant) decimal digits of $x$ = 2^(3^(4^(5^(6^(7^(8^9)))))).

First some notation. Let

$x_n = n^{(n+1)^{(n+2)^{.^{.^{.^9}}}}}$

denote the tower beginning at the integer base $n$ and ending at 9. So,

$x_2 = 2^{3^{4^{.^{.^{.^9}}}}}$,

$x_3 = 3^{4^{5^{.^{.^{.^9}}}}}$,

$x_4 = 4^{5^{6^{.^{.^{.^9}}}}}$ and so on.

The obvious way to find the digits is to reduce $x_2$ modulo $10^{10}$. The first thing I thought of is Euler's theorem. But the base (2) and the modulus ($10^{10}$) are not coprime. So the next tool to use is the Chinese remainder theorem.

  • $10^{10}=2^{10}5^{10}$
  • $x_2$ mod $2^{10}$ is zero because the exponent of 2 is larger than 10.
  • $x_2$ mod $5^{10}$ can be found using Euler's theorem.
  • Now reduce $x_3$ modulo $\phi(5^{10})=5^{10}-5^9=2^25^9.$
  • 3 is coprime to both 2 and 5 so we can apply Euler's theorem again.
  • Now reduce $x_4$ modulo $\phi(\phi(5^{10}))=\phi(5^{10}-5^9)=\phi(2^25^9)=(2^2-2)(5^9-5^8)....$

This becomes repetitive, confusing, and messy real fast because you have to keep track of everything as you climb up the tower and then put everything together as you come back down. I see that you only have to climb up to where the base is 5 but I am convinced that there must be a faster and a more elegant solution.

My question is, what is the fastest/most-elegant way to solve this problem? I have been wrestling with this for weeks and I do have the digits. But is there a particular trick or insight that I am missing here? If yes, then what is it?

I would prefer that the solution doesn't require anything beyond a standard-undergrad-intro-to-number-theory course, paper, pencil, and a basic calculator (to calculate powers quickly, etc.) but any tricks/shortcuts are welcome.

$\endgroup$
  • $\begingroup$ It would be a little clearer if you used $n$ or $k$ rather than $i$ for the integer index, because $i$ risks confusion with the imaginary number $i$. $\endgroup$ – hardmath Feb 27 '17 at 23:21
  • 4
    $\begingroup$ The method is exactly correct. In order to know $x_k\bmod N$, you need to know $x_{k+1}\bmod\phi(N)$ ($\pm$Chinese remainder) $\endgroup$ – Hagen von Eitzen Feb 27 '17 at 23:27
  • $\begingroup$ @HagenvonEitzen A perfectly valid answer. $\endgroup$ – Fixed Point Mar 2 '17 at 19:26
3
$\begingroup$

We know that $2^{x_3} \bmod 10^{10}$ will cycle on a loop that divides Carmichael function $\lambda(5^{10})=4\cdot 5^9 =: m_3$, provided $x_3\ge 10$ for the multiplicity of $2$ in $10^{10}$.

Then $3^{x_4} \bmod m_3$ cycles on a loop dividing $\lambda(m_3) = 4\cdot 5^8 =:m_4$

$4^{x_5} \bmod m_4$ cycles on a loop dividing $\lambda(m_4) = 4\cdot 5^7 :=m_5$

However $5^{x_6} \bmod m_4$ cycles on a loop dividing $4$, provided the exponent is taken as at least $7$, since the cycling will run on multiples of $5^7$ beyond that point.

Then $6^{x_7} \equiv 0 \bmod 4$, so we will need to use $8\equiv 0 \bmod 4$ in the above.

Falling back down the tree, $5^8 \equiv 78125 \bmod m_5$ (and it actually transpires that this is a fixed value, $5^9 \equiv 78125 \bmod m_5$ also).

From here we'll potentially need to use exponentiation by squaring or similar technique to get modular values.

$4^{78125 } \equiv 110443 \bmod m_4$
$3^{110443 } \equiv 3809764 \bmod m_3$

And with a bit of difficulty,
$2^{3809764 } \equiv 9540755456 \bmod 10^{10}$

should be our result. No really clever tricks beyond what you already know, I'm guessing, and not a hand-calculation I would volunteer for. Fortunately I already had some tools for the steps here.

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