# how to compute the last 2 digits of 3^3^3^3 to n times?

input n, output the last 2 digits of the result.

n=1 03 3=3
n=2 27 3^3=27
n=3 87 3^27=7625597484987
n=4 ?? 3^7625597484987=??


Sorry guys, the formula given is T(n)=3^(T(n-1)), I have updated the example. I was asked this question during an interview, but I didn't have any clue. (The interviewer kind of gave me a hint that for n>10, the last 10 digits of all results would be the same?)

-
you sure you meant 3^3 = 09? for n=2 –  Kailas Mar 12 '14 at 7:11
yeah, should be 27, thanks for pointing out. –  Simon Mar 12 '14 at 7:13
3^3^3^3 is not 7625597484987 –  bobbym Mar 12 '14 at 7:15
You need to put some parentheses there. $3^{3^3}\neq \left(3^3\right)^3$ . So this is just $3^{3n}$. Do you have some idea about Modular Arithmetic? –  chubakueno Mar 12 '14 at 7:17
@bobbym Yes it is. It's ((3^3)^3)^3 –  Thanos Darkadakis Mar 12 '14 at 7:19

Notice $$3^{100} = 515377520732011331036461129765621272702107522001 \equiv 1 \pmod{100}$$ If we define $p_n$ such that $p_1 = 3$ and $p_n = 3^{p_{n-1}}$ recursively and split $p_n$ as $100 q_n + r_n$ where $q_n, r_n \in \mathbb{Z}$, $0 \le r_n < 100$, we have

$$p_n = 3^{p_{n-1}} = 3^{100 q_{n-1} + r_{n-1}} \equiv 1^{q_{n-1}}3^{r_n} \equiv 3^{r_{n-1}} \pmod{100} \\ \implies r_n \equiv 3^{r_{n-1}} \pmod{100}$$

This means to obtain $r_n$, the last two digit of $p_n$, we just need to start with $r_1 = 3$ and repeat iterate it. We find \begin{align} r_1 &= 3\\ r_2 &\equiv 3^3 = 27 \pmod{100}\\ r_3 &\equiv 3^{3^3} = 7625597484987 \equiv 87 \pmod{100} \end{align}

Notice $$3^{87} = 323257909929174534292273980721360271853387 \equiv 87 \pmod{100}$$

So after the third (not fourth) iteration, we have $r_n = 87$ for all $n \ge 3$.

-
Thank you, I think this is the answer, still trying to understand –  Simon Mar 12 '14 at 8:04
Got it! Thanks everyone. –  Simon Mar 12 '14 at 8:12
A remark: This would happen for any other base and modulus, not just $3$ and $100$ . Since $f(n)=b^n\pmod k$ has periodicity $<k$, the periodicity for each level of the power tower is always less than the previous one, and we would eventually reach periodicity one, guaranteeing that eventually the sequence will "stall". –  chubakueno Mar 12 '14 at 8:16
In particular, the periods here happen to be $20,4,2,1$ (because $3^{20}\equiv1\pmod{100}, 3^4\equiv1\pmod{20}, 3^2\equiv1\pmod4,3\equiv1\pmod2$ ) –  chubakueno Mar 12 '14 at 8:23

These are the last 2 digits of $3^m$ for $m\in\{0..19\}$

01,03,09,27,81,43,29,87,61,83,49,47,41,23,69,07,21,63,89,67
Let's call this A: A[0]=01, A[1]=03, A[19]=67...


These numbers are repeated for every 20 numbers. i.e. $3^{20+x}$ mod 100=$3^x$ mod 100

Your sequence of numbers simplified is: $3^{3^{n-1}}$.

For example for n=4: $a_4=((3^3)^3)^3=(3^3)^{3*3}=3^{3*3*3}$ using that $(x^a)^b=x^{ab}$

So, you just have to find the exponent modulo 20. i.e $3^{n-1}$ mod 20

These are the remainder (modulo 20) of $3^m$ for $m\in\{0..3\}$

1,3,9,7


These numbers are repeated for every 4 numbers. i.e. $3^{4+x}$ mod 20=$3^x$ mod 20

So what you need is:

• A[1]=03 (=B[1])
• A[3]=27 (=B[2])
• A[9]=83 (=B[3])
• A[7]=87 (=B[0])

These numbers are repeated. So in order to find an answer for a given n, you will have to compute n mod 4 and then get B[n mod 4].

-
Thank you very much for the answer, could you please help me the updated question? formula is T(n)=3^(T(n-1)) –  Simon Mar 12 '14 at 7:54
I added an example of why this is true for n=4. You can make generic for n –  Thanos Darkadakis Mar 12 '14 at 8:35

There is a stronger argument $3^{100}\equiv 1 \pmod{1000}$ and by induction $3^{10^{n}}\equiv 1 \pmod{10^{n+1}}$, $\forall n \geq 2$, because: $$3^{10^{n+1}}-1=3^{10 \cdot 10^{n}}-1=(3^{10^{n}}-1)\cdot(3^{9 \cdot 10^{n}} + 3^{8 \cdot 10^{n}} + ... + 3^{1 \cdot 10^{n}} + 1)=(3^{10^{n}}-1)\cdot(3^{9 \cdot 10^{n}}-1 + 3^{8 \cdot 10^{n}}-1 + ... + 3^{1 \cdot 10^{n}}-1 + 10)$$

Obviously, this also implies $3^{10^{n}}\equiv 1 \pmod{10^{n}}$, $\forall n \geq 2$

Next thing to observe is: if $3^{x}\equiv y \pmod{10^{n}}$ $\Rightarrow$ $3^{3^{x}} \equiv 3^{y} \pmod{10^{n+1}}$, $\forall n\geq 2$

Because, from $3^{x}=10^{n} \cdot q +y$ $\Rightarrow$ $3^{3^{x}} = 3^{10^{n} \cdot q +y}$ and using first result $3^{10^{n} \cdot q} \equiv 1^{q} \equiv 1 \pmod{10^{n+1}}$ we have $3^{3^{x}} \equiv 3^{y} \pmod{10^{n+1}}$.

Now, that $t_{3} \equiv 87 \pmod{100}$ $\Rightarrow$ $t_{4} \equiv 3^{87} \pmod{1000}$ and (easy to show) $3^{87} \equiv 387 \pmod{1000}$, i.e. $t_{4} \equiv 387 \pmod{1000}$.

Also $t_{5} = 3^{t_{4}} \equiv 3^{1000 \cdot q + 387} \equiv 3^{387} \equiv 3^{100 \cdot 3 + 87} \equiv 3^{87} \equiv 387 \pmod{1000}$.

As a result, $$t_{5} \equiv t_{4} \pmod{10^3}$$ $$t_{6} \equiv t_{5} \pmod{10^4}$$ $$t_{7} \equiv t_{6} \pmod{10^5}$$ $$...$$ $$t_{n+2} \equiv t_{n+1} \pmod{10^{n}}$$ But we can stop at: $$t_{12} \equiv t_{11} \pmod{10^{10}}$$ $$t_{13} \equiv t_{12} \pmod{10^{11}}\Rightarrow t_{13} \equiv t_{12} \pmod{10^{10}}\Rightarrow t_{13} \equiv t_{11} \pmod{10^{10}}$$ $$...$$

That's, more or less, the proof for "(The interviewer kind of gave me a hint that for n>10, the last 10 digits of all results would be the same?)"

-