# CMC - Problem 9

Problem 9. (8 points) Let $a_n$ be a sequence such that $a_1=2,a_2=k$ for some $k$ and for all $n\ge3$, $a_n=a_{n-1}^{a_{n-2}}$. Let $p,q,r,s$ be the values of $a_{1024}$ where $k=4,5,6,7$, respectively. Find the last two digits of $p+q+r+s$.

Note by Cody Johnson
6 years, 4 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I think it's 46.

- 6 years, 4 months ago

I do it this way. I start with $k=4$. First we try small numbers first.

$a_1 = 2, a_2 = 4, a_3 = 4^2 = 16, a_4 = 16^4 = 65536 \overline= 36 (mod 100), a_5 = 65536^{16} ...$

It would be laborious for us to calculate term $a_5$, so we try to trace the pattern, by testing some small values.

$36^1 = 36$

$36^2 = 1296 \overline= 96 (mod 100)$

$36^3 \overline= 96 \times 36 (mod 10000) \overline= 56 (mod 100)$

$36^4 \overline= 56 \times 36 (mod 10000) \overline = 16 (mod 100)$

$36^5 \overline= 16 \times 36 (mod 10000) \overline = 76 (mod 100)$

$36^6 \overline= 76 \times 36 (mod 10000) \overline = 36 (mod 100)$,

$36^7 \overline= 36 \times 36 (mod 10000) \overline = 96 (mod 100)$,

and so on. Obviously, the pattern recurs every 5 terms. Since $16 \overline= 1 (mod 5)$, so last two digits of $65536^{16}$ is $36$. Thus, we have $36$ as the last two digits of $p$, since no matter what happens, we have $6$ as the last digit of every term except term $a_1$ and $a_2$, and $6 \overline= 1 (mod 5)$.

Then, when $k = 5$, we have

$a_1 = 2, a_2 = 5, a_3 = 5^2 = 25, a_4 =25^5 ...$

Since $25^5$ is very hard to calculate, so we try to trace the pattern again,

$5^1 = 5$

$5^2 = 25$

$5^3 = 125$

$5^4 =625$

and so on. Starting from $5^2$, last two digits are $25$. Thus, $25^5$ has $25$ as the last two digits, so as the term $a_5 = 25^{25}$. Therefore, $q$ has $25$ as the last two digits.

Then, when $k = 6$, we have

$a_1 = 2, a_2 = 6, a_3 = 6^2 = 36, a_4 = 36^6 \overline= 36(mod 100), a_5 \overline= 36 (mod 100) ...$.

Hey! This case is almost the same as when $k=4$! So, last digits of $r = 36$

Finally, when $k=7$, we have

$a_1 = 2, a_2 = 7, a_3 = 7^2 = 49, a_4 = 49^7 ...$

Again, for the last time in this problem, we trace the pattern.

$49^1 = 49$

$49^2 = 2401$

$49^3 \overline= 01 \times 49 (mod 100) \overline = 49 (mod 100)$

$49^4 \overline= 49 \times 49 (mod 10000) \overline = 01 (mod 100)$

and so on. Obviously, the pattern recurs every two terms. Since $7 \overline= 1(mod 2)$, so $49^7 \overline= 49(mod 100)$, so as term $a_5 = 49^{343} \overline= 49(mod 100)$. This implies that $r$ has last two digits of $49$.

In the end, $p+q+r+s = 36+25+36+49 \overline= \boxed {46}(mod 100)$.

- 6 years, 4 months ago

Some Latex suggestions. Use:

\pmod n

which comes out as $\pmod n$ which looks nicer.

- 6 years, 4 months ago

Okay, I appreciate that and I will remember that

- 6 years, 4 months ago

Correct! 8 points for you!

- 6 years, 4 months ago

The last two digits of P=36,Q=25,R=36,S=49.Thus Last two digits of P+Q+R+S=46

- 6 years, 4 months ago

Can you explain the second sentence? Do you mean that $a_{1024}$has $4$ possible values or other thing else?

- 6 years, 4 months ago

When $k = 4$ , $a_{1024} = p$ and when $k = 5$ , $a_{1024} = q$ and so on .

- 6 years, 4 months ago

Okay, I got it. Thanks.

- 6 years, 4 months ago

i dont know sir can u liease teach me i will be very glad to get teachings from you

- 6 years, 4 months ago

Okay, first of all, I start with $k=4$. Then, we follow the rules to define the next term of the sequence, we have $a_1 = 2, a_2 = k = 4, a_3 = a_{(3-1)}^{a_{(3-2)}} = a_2^{a_1} = 4^2 = 16, \text{and } a_4 = 16^4 = 65536$. So, why I write $65536 \overline= 36 \pmod {100}$ is because $100|65536 - 36$. So, you may ask me why I can't try $136, 236$ or bigger, yes, you can. But remember we need last two digits. It is all about Modular Arithmetic. So, if you don't understand or don't know what is Modular Arithmetic, click on the link. (By the way, you have to understand the main property of modular, that is when $a\overline= b \pmod n$, that means $n|a-b$.)

Now, let's move on to the line 7. (I expect you understand line 5 and 6) It would be laborious for us to calculate $36^3$ (In this competition, it is stated clearly that calculator or any calculating program is prohibited, so this way is faster and better), so I take the last two digits of 1296, which is 96, then since $36^3$ is equal to 36 times of 1296, so I multiply 96 with 36, and this process goes on and on (But I stopped it when it reaches $36^7$, since it is enough to prove that the pattern of the last two digits is recursive). So, you may ask me why I write $\pmod {10000}$ instead of $\pmod{100} \text{ or } \pmod{1000}$, from line 7 to line 12. Yes, you can, if you want to, there is no right and wrong about that, as long as your statement satisfy the main property I listed out. Okay, back to the solution, as we know, $6 \overline= 1\pmod5$, so from here it indicates the first term in the pattern. Therefore, $p$ has 36 as its last two digits, since the exponent ends with 6.

Then, we now move on to the case when $k=5$. Do you realize that except term $a_1$ and $a_2$, all of them ends with 25. This implies to every term and $q$ execpt term $a_1$ and $a_2$ has 25 as the last two digits.

Alright, for the case when $k=6$ and $k=7$, I use the same way, even though the case when $k=6$, I skipped a lot, since the exponent ends with 6, just like when $k=4$. Finally, sum up $p+q+r+s$, we have 46 as the last two digits.

So, I had try my best to explain, I hope you had understand. This question tests you Pattern Recognition the most, since you have to check out the pattern what has happened to the last two digits when the exponents are different. Otherwise, if you choose to use brute force, then you will have to calculate for 1024 times, that would drive you nuts. (I can't imagine what is the real value of $a_{1024}$...)

- 6 years, 4 months ago