HMMT-Nov 2014 guts, Problem 19

Let a sequence $\left\{a_{n}\right\}_{n=0}^{\infty}$ be defined by $a_{0}=\sqrt{2}, a_{1}=2$, and $a_{n+1}=a_{n} a_{n-1}^{2}$ for $n \geq 1$. The sequence of remainders when $a_{0}, a_{1}, a_{2}, \cdots$ are divided by 2014 is eventually periodic with some minimal period $p$ (meaning that $a_{m}=a_{m+p}$ for all sufficiently large integers $m$, and $p$ is the smallest such positive integer). Find $p$.

Solution: Let $a_{n}=2^{b_{n}}$, so notice $b_{1}=1, b_{2}=2$, and $b_{n+1}=b_{n}+2 b_{n-1}$ for $n \geq 1$, so by inspection $b_{n}=2^{n-1}$ for all $n$; thus $a_{n}=2^{2^{n-1}} .2014=2 \cdot 19 \cdot 53$ so we just want to find the lcm of the eventual periods of $2^{n} \bmod \operatorname{ord}_{19}(2)$ and $\operatorname{ord}_{53}(2)$. These orders divide 18 and 52 respectively, and we can manually check $\operatorname{ord}_{9}(2)=6$ and $\operatorname{ord}_{13}(2)=12$. The $1 \mathrm{~cm}$ of these is 12 , so to show the answer is 12 , it suffices to show that $13 \mid \operatorname{ord}_{53}(2)$. This is true since $2^{4} \not \equiv 1(\bmod 53)$. So, the answer is 12 . $\fbox{12}$.

Answer: 12