2 To The 2 To The 2 To The 2 To The Ad Infinitum

Number Theory Level 4

$\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)$ .

Proving that the terms of $\{b_{n}\}$ become constant is an old USAMO problem, which inspired this problem.

The answer is 8.

2 solutions

Xuming Liang
Feb 14, 2016

Relevant wiki: Euler's Theorem

We will use the following observations to compute $f(n)$ :

Prime factorize $n=p_{1}^{e_1}p_{2}^{e_2}...p_{k}^{e_k}$ , then $f(n)=\text {max}\{f(p_{1}^{e_1}),f(p_{2}^{e_2}),...,f(p_{k}^{e_k})\}$
For prime odd $p$ and positive integer $e$ , we have $f(p^e)=f(\text {ord}_{p^e}(2))+1$

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}$ .

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

How would you have phrase this question then?

Pi Han Goh - 5 years, 4 months ago

$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

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

Pi Han Goh - 5 years, 4 months ago

@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.

Calvin Lin Staff - 5 years, 3 months ago

@Calvin Lin – @Calvin Lin

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

@Zk Lin – Thanks, edited the typo.

Calvin Lin Staff - 5 years, 3 months ago

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

Otto Bretscher - 5 years, 3 months ago

@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$ .

Calvin Lin Staff - 5 years, 3 months ago

@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

@Otto Bretscher – Agreed. I'm playing devil's advocate to the strength / completeness / rigour of a solution.

Calvin Lin Staff - 5 years, 3 months ago

Zk Lin
Feb 17, 2016

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.

Moderator note:

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.

2 To The 2 To The 2 To The 2 To The Ad Infinitum

Proving that the terms of { b n } \{b_{n}\} { b n ​ } become constant is an old USAMO problem, which inspired this problem.

The answer is 8.

2 solutions

Moderator note:

0 pending reports

Proving that the terms of $\{b_{n}\}$ become constant is an old USAMO problem, which inspired this problem.