Towers of 2

Number Theory Level 3

Define a sequence $T_{k}$ such that ${T_{1} = 2}$ and ${T_n = 2^{T_{n-1}}}$ .

Find the remainder when ${T_1 + T_2 + T_3 +\ldots + T_{256}}$ is divided by 255.

This is not an original problem.

The answer is 20.

1 solution

Sagnik Saha
Apr 20, 2014

We have

$T_1 = 2$

$T_2 = 4$

$T_3 = 16$

Now, all terms after $T_3$ is a power of $2^8 = 256$ . And $256 \equiv 1 \mod{255}$ .

Therefore all of $T_4 , T_5 , ... T_{256}$ leave a remainder $1$ when divided by $255$ .

So the required remainder is $T_1 + T_2 + T_3 + 1 \times 253$ = $2 + 4 + 13 + 253 \mod{255}$ = $20 \mod{255}$ . Hence our answer is $\boxed{20}$

Small typo at the end: 16 not 13

Xuming Liang - 7 years, 1 month ago

Can you explain clearly why "Therefore all of $T_4 , T_5 , ... T_{256}$ leave a remainder $1$ when divided by $255$ ."? While the statement is true, I do not see any justification as yet.

Calvin Lin Staff - 7 years, 1 month ago

Because all the $T_i$ where $i \geq 4$ is a power of $256$ and $256 \equiv 1 \mod{255}$ so any power of $256$ is also $1 \mod{255}$

Sagnik Saha - 7 years, 1 month ago

Ah, why is it a power of 256? If we had $T_n = T_{n-1} ^ 2$ , then it's clear that if $T_i = 256$ then any higher term will be a power of 256. However, because $T_n = 2^{T_n-1}$ , this is not immediately obvious. That is the justification that I am asking for. Why do we know that $T_n = 256^{S_n}$ ?

Calvin Lin Staff - 7 years, 1 month ago

Isn't this a simple induction? Let $T_{n-1}=256^a$ . Then $T_n=2^{256^a}=2^{256^{a-1}*32*8}={(2^8)}^{32.256^{a-1}}=256^{32.256^{a-1}}$

ww margera - 6 years, 8 months ago

Towers of 2

This is not an original problem.

The answer is 20.

1 solution

0 pending reports