Olympiad Maths Prep

Track / Stage 6 / 195 of 400 #1195 of 2000

Problem 1195

National olympiad, first round
Number theory Difficulty 6.3 Find the answer

Define a sequence of integers by T1=2T_1 = 2 and for n2n\ge2, Tn=2Tn1T_n = 2^{T_{n-1}}. Find the remainder when T1+T2++T256T_1 + T_2 + \cdots + T_{256} is divided by 255.

[i]Ray Li.[/i]

Official solution

1. First, we define the sequence Tn T_n as given:
T1=2 T_1 = 2
T2=2T1=22=4 T_2 = 2^{T_1} = 2^2 = 4
T3=2T2=24=16 T_3 = 2^{T_2} = 2^4 = 16
T4=2T3=216 T_4 = 2^{T_3} = 2^{16}

2. For n4 n \geq 4 , Tn=2Tn1 T_n = 2^{T_{n-1}} becomes extremely large. We need to consider these terms modulo 255. Notice that:
2161(mod255) 2^{16} \equiv 1 \pmod{255}
This is because 216=65536 2^{16} = 65536 and 65536mod255=1 65536 \mod 255 = 1 .

3. Since T4=2161(mod255) T_4 = 2^{16} \equiv 1 \pmod{255} , for n4 n \geq 4 , Tn1(mod255) T_n \equiv 1 \pmod{255} .

4. Now, we need to sum the first 256 terms of the sequence modulo 255:
T1+T2+T3+T4++T256 T_1 + T_2 + T_3 + T_4 + \cdots + T_{256}

5. We know:
T1=2,T2=4,T3=16 T_1 = 2, \quad T_2 = 4, \quad T_3 = 16
and for n4 n \geq 4 , Tn1(mod255) T_n \equiv 1 \pmod{255} .

6. Therefore, the sum can be broken down as:
T1+T2+T3+n=4256Tn T_1 + T_2 + T_3 + \sum_{n=4}^{256} T_n
=2+4+16+n=42561 = 2 + 4 + 16 + \sum_{n=4}^{256} 1

7. The number of terms from T4 T_4 to T256 T_{256} is 2564+1=253 256 - 4 + 1 = 253 .

8. Thus, the sum is:
2+4+16+253×1 2 + 4 + 16 + 253 \times 1
=2+4+16+253 = 2 + 4 + 16 + 253
=275 = 275

9. Finally, we find the remainder when 275 is divided by 255:
275mod255=20 275 \mod 255 = 20

The final answer is 20\boxed{20}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.