$\large 2,2^2,2^{2^2},2^{2^{2^2}},\ldots$ The sequence above can be recursively defined by $a_1=2, a_{k+1}=2^{a_{k}}$

Given a positive integer $n$ , a new sequence is created by dividing each term $\{a_k\}$ by $n$ and writing down the remainder of the division. We denote this new sequence by $\{b_{k}\}$ .

For a given $n$ , it is known that the terms of $\{b_{k}\}$ eventually become constant. Let $f(n)$ denote the index at which the constant values begin, i.e. $f(n)$ is the smallest number $i$ for which $b_{i-1} \neq b_i = b_{i+1} = b_{i+2} = \cdots$ .

Find $f(2016)+f(2015)$ .

The answer is 8.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Once we understand what the problem asks (which I didn't), it's not that hard.

We can use the Carmichael Lambda and Euler's Theorem; note that $\lambda(2015)=60, \lambda(60)=4, \lambda(2016)=24$ and $\lambda(24)=2$ .

Now we have, for any positive integer $n$ ,

$2^{2^n}\equiv 2^2 \pmod{4}$ so $2^{2^{2^n}}\equiv 2^{2^2} \pmod{60}$ and $2^{2^{2^{2^n}}}\equiv 2^{2^{2^2}}\pmod{2015}$

Likewise,

$2^{2^n}\equiv 2^2 \pmod{2}$ so $2^{2^{2^n}}\equiv 2^{2^2} \pmod{24}$ and $2^{2^{2^{2^n}}}\equiv 2^{2^{2^2}}\pmod{2016}$

We can quickly verify that $2^{2^2}=16$ isn't congruent to $2^{2^{2^2}}=65536$ modulo 2015 or 2016.

Thus $f(2015)=f(2016)=4$ and the answer is 8.

Otto Bretscher
- 5 years, 4 months ago

Log in to reply

How would you have phrase this question then?

Pi Han Goh
- 5 years, 4 months ago

Log in to reply

$n$ is used with different meanings: $a_n$ and $b_n$ vs modulo $n$ ... using different letters would help.

Otto Bretscher
- 5 years, 4 months ago

Log in to reply

@Otto Bretscher – @Xuming Liang , what do you think?

Pi Han Goh
- 5 years, 4 months ago

Log in to reply

@Pi Han Goh – Thanks. I've edited the indices in the problem.

I agree that we should avoid having notation do double duty. You don't want to sit through a lecture where all the variables are "a", just of different size.

Log in to reply

Shouldn't $b_{i+1} \neq b_i = b_{i+1} = b_{i+2} = \cdots$ be

$b_{i-1} \neq b_i = b_{i+1} = b_{i+2} = \cdots$ ?

ZK LIn
- 5 years, 3 months ago

@Calvin Lin – BTW, @Calvin Lin , does my (rather short) solution make sense?

Otto Bretscher
- 5 years, 3 months ago

Log in to reply

@Otto Bretscher – Yes it does. Though, rather than Carmichael Lambda, we actually want something like the "order" of 2 power. You have only shown that 4 is the upper bound, and we still have to check that it is the minimum.

For example, if 2 was replaced by 1, then the answer is clearly $f(2015) = f(2016) = 1$ .

Log in to reply

@Calvin Lin – Thanks for your comments, @Calvin Lin

Yes, of course, we need to verify that $2^{2^2}=16$ isn't congruent to $2^{2^{2^2}}=65536$ modulo 2015 or 2016; I will add this remark to my solution.

I agree that "in general" we want to think about the order of 2, but in this rather simple case we can get away with the Carmichael Lambda, which makes the solution much shorter and simpler.

Otto Bretscher
- 5 years, 3 months ago

Log in to reply

To find $f(2016)$ , write:

$a_{n+1}-a_{n}=2016k$ .

$2^{a_{n}}-2^{a_{n-1}}=2016k$

$2^{a_{n-1}}(2^{a_{n}-a_{n-1}}-1)=63.2^{5}.k$

Note that we must have

$2^{a_{n}-a_{n-1}} \equiv 1 \pmod{63}$

By Euler's theorem, since $\gcd(2,63)=1$

$a_{n}-a_{n-1} \equiv 0 \pmod{\phi(63)}$ is a sufficient but unnecessary condition for the congruence above to hold.

Compute $\phi(63)=\phi(7)\phi(3^{2})=6(3^{2}-3)=36$

Note that $a_{4}-a_{3}=2^{2^{2^{2}}}-2^{2^{2}}=2^{2^{2}}(2^{2^{2^{2}}-2^{2}}-1)=16(2^{12}-1)$

Since $2^{3} \equiv -1 \pmod{9}$ , we have $2^{12} \equiv {(2^{3})}^{4} \equiv 1 \pmod{9}$ .

Therefore, $a_{4}-a_{3}=16(2^{12}-1)=16(9q)=36(4q)$ .

We check that $a_{5}-a_{4}=2^{a_{3}}(2^{a_{4}-a{3}}-1)=2^{16}(63p)=2^{11}(2016p)$ , which follows from Euler's theorem.

It is fairly easy to show that $a_{4}-a_{3}$ is not divisible by $2016$ . Note that

$a_{4}-a_{3}\ = 2^{a_{2}}(2^{a_{3}-a_{2}}-1)= 16m$ , where $m$ is an odd number. However, $2016=32.63$ , so obviously, $a_{4} \neq a_{3} \pmod{2016}$ . We conclude that $f(2016)=4$ .

To find $f(2015)$ , write

$a_{n+1}-a_{n}=2015k$ .

$2^{a_{n}}-2^{a_{n-1}}=2015k$

$2^{a_{n-1}}(2^{a_{n}-a_{n-1}}-1)=2015k$

Note that we must have

$2^{a_{n}-a_{n-1}} \equiv 1 \pmod{2015}$

By Euler's theorem, since $\gcd(2,2015)=1$

$a_{n}-a_{n-1} \equiv 0 \pmod{\phi(2015)}$ is a sufficient but unnecessary condition for the congruence above to hold.

Compute $\phi(2015)=\phi(5)\phi(13)\phi(31)=4.12.30=1440$

Therefore, we obtain $a_{n}-a_{n-1} \equiv 0 \pmod{1440}$

$2^{a_{n-2}}(2^{a_{n-1}-a_{n-2}}-1)=1440k=32.45k$

For the congruence to hold, note that $(2^{a_{n-1}-a_{n-2}}-1)\equiv 0 \pmod{45}$ .

By Euler's theorem, since $\gcd(2,45)=1$

$a_{n-1}-a_{n-2} \equiv 0 \pmod{\phi(45)}$ is a sufficient but unnecessary condition for the congruence above to hold.

Compute $\phi(45)=\phi(5)\phi(3^{2})=4.(3^{2}-3)=24$

Note that $a_{4}-a_{3}=2^{2^{2^{2}}}-2^{2^{2}}=2^{2^{2}}(2^{2^{2^{2}}-2^{2}}-1)=16(2^{12}-1)=16(4095)=24(2730)$ .

We check that

$2^{a_{3}}(2^{a_{4}-a_{3}}-1)=2^{16}(45k)=1440(2048k)$

Therefore, $a_{5}-a_{4}=2^{a_{3}}(2^{a_{4}-a_{3}}-1)=2^{16}(2015r)$ follows from Euler's theorem.

It is fairly easy to show that $a_{4}-a_{3}$ is not divisible by $2015$ . Note that

$a_{4}-a_{3}\ = 2^{a_{2}}(2^{a_{3}-a_{2}}-1)= 16(2^{12}-1)=16(2.2015+65)=32.2015+1040$ .

Therefore, we conclude that $f(2015)=4$ .

$f(2015)+f(2016)=4+4=\boxed{8}$ and we are done.

2 Helpful
0 Interesting
0 Brilliant
0 Confused

Great! Very detailed explanation.

Note that instead of "unnecessary condition", what you mean is that it is "not a necessary condition". I've not seen the latter expressed in the former way, though I can infer what you mean.

×

Problem Loading...

Note Loading...

Set Loading...

Relevant wiki: Euler's TheoremWe will use the following observations to compute $f(n)$ :

The first point is motivated by the chinese remainder theorem . Since $a\equiv b\pmod {n} \implies a\equiv b\pmod {p_{i}^{e_i}}$ because $p_{i}^{e_i}|n$ , it is necessary for the $\{b\}$ sequence of ${p_{i}^{e_i}}$ to start repeating the same value before the $\{b\}$ sequence of $n$ . By this reasoning, we have $f(n)\ge f(p_{i}^{e_i})$ for all $i=1,2,...,k$ .

For the second point, we make use of a property of order : $2^a\equiv 2^b\pmod {p^e}\iff a\equiv b\pmod {\text {ord}_{p^e}(2)}$ . For our problem specifically, we have $a_i\equiv a_{i+1} \pmod {p^e} \iff a_{i-1}\equiv a_{i} \pmod {\text {ord}_{p^e}(2)}$ In other words, the terms of $\{b\}$ wrt $p^e$ repeats one index after those of $\{b\}$ wrt $\text {ord}_{p^e}(2)$ , hence the recursive formula is justified.

As a example, we can compute $f(2016)$ as follows:

$f(2^5)=4$

$f(3^2)=f(6)+1=f(3)+1=f(2)+2=3$

$f(7)=f(3)+1=3$

Thus $f(2016)=\text {max}\{f(2^5),f(3^2),f(7)\}=4$

In a similar fashion, we can find $f(2015)=4$ . Hence the answer is $4+4=\boxed {8}$ .