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 at 7:11
    
yeah, should be 27, thanks for pointing out. –  Simon Mar 12 at 7:13
    
3^3^3^3 is not 7625597484987 –  bobbym Mar 12 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 at 7:17
    
@bobbym Yes it is. It's ((3^3)^3)^3 –  Thanos Darkadakis Mar 12 at 7:19

2 Answers 2

up vote 2 down vote accepted

Notice $$3^{100} = 515377520732011331036461129765621272702107522001 = 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}} = 1^{q_{n-1}}3^{r_n} = 3^{r_{n-1}} \pmod{100} \\ \implies r_n = 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 &= 3^3 = 27 \pmod{100}\\ r_3 &= 3^{3^3} = 7625597484987 = 87 \pmod{100} \end{align}$$

Notice $$3^{87} = 323257909929174534292273980721360271853387 = 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 at 8:04
    
Got it! Thanks everyone. –  Simon Mar 12 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 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 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].

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 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 at 8:35

Your Answer

 
discard

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.