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?)

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

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].

There is a stronger argument:

$3^{100}\equiv 1 \pmod{1000}$ and by induction

Proposition 1. $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

Proposition 2. $3^{10^{n}}\equiv 1 \pmod{10^{n}}, \forall n \geq 2$

Next thing to observe is:

Proposition 3. 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}$$ $$...$$ and by induction

$$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?)"