Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
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\}$

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


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

share|improve this answer
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?)"

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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