Problem 2. Let $m$ be a fixed positive integer. The infinite sequence $\left\{a_{n}\right\}_{n \geq 1}$ is defined in the following way: $a_{1}$ is a positive integer, and for every integer $n \geq 1$ we have
$$
a_{n+1}=\left\{\begin{array}{ll}
a_{n}^{2}+2^{m} & \text { if } a_{n}<2^{m} \\
a_{n} / 2 & \text { if } a_{n} \geq 2^{m} .
\end{array}\right.
$$

For each $m$, determine all possible values of $a_{1}$ such that every term in the sequence is an integer.
Answer: The only value of $m$ for which valid values of $a_{1}$ exist is $m=2$. In that case, the only solutions are $a_{1}=2^{\ell}$ for $\ell \geq 1$.

Solution. Suppose that for integers $m$ and $a_{1}$ all the terms of the sequence are integers. For each $i \geq 1$, write the $i$ th term of the sequence as $a_{i}=b_{i} 2^{c_{i}}$ where $b_{i}$ is the largest odd divisor of $a_{i}$ (the "odd part" of $a_{i}$ ) and $c_{i}$ is a nonnegative integer.
Lemma 1. The sequence $b_{1}, b_{2}, \ldots$ is bounded above by $2^{m}$.

Proof. Suppose this is not the case and take an index $i$ for which $b_{i}>2^{m}$ and for which $c_{i}$ is minimal. Since $a_{i} \geq b_{i}>2^{m}$, we are in the second case of the recursion. Therefore, $a_{i+1}=a_{i} / 2$ and thus $b_{i+1}=b_{i}>2^{m}$ and $c_{i+1}=c_{i}-1m$, then $a_{i+1}=2^{m}\left(b_{i}^{2} 2^{2 c_{i}-m}+1\right)$, so $b_{i+1}=b_{i}^{2} 2^{2 c_{i}-m}+1>b_{i}$.
- If $2 c_{i}b_{i}$.
- If $2 c_{i}=m$, then $a_{i+1}=2^{m+1} \cdot \frac{b_{i}^{2}+1}{2}$, so $b_{i+1}=\left(b_{i}^{2}+1\right) / 2 \geq b_{i}$ since $b_{i}^{2}+1 \equiv 2(\bmod 4)$.
By combining these two lemmas we obtain that the sequence $b_{1}, b_{2}, \ldots$ is eventually constant. Fix an index $j$ such that $b_{k}=b_{j}$ for all $k \geq j$. Since $a_{n}$ descends to $a_{n} / 2$ whenever $a_{n} \geq 2^{m}$, there are infinitely many terms which are smaller than $2^{m}$. Thus, we can choose an $i>j$ such that $a_{i}<2^{m}$. From the proof of Lemma $2, a_{i}<2^{m}$ and $b_{i+1}=b_{i}$ can happen simultaneously only when $2 c_{i}=m$ and $b_{i+1}=b_{i}=1$. By Lemma 2 , the sequence $b_{1}, b_{2}, \ldots$ is constantly 1 and thus $a_{1}, a_{2}, \ldots$ are all powers of two. Tracing the sequence starting from $a_{i}=2^{c_{i}}=2^{m / 2}<2^{m}$,
$$
2^{m / 2} \rightarrow 2^{m+1} \rightarrow 2^{m} \rightarrow 2^{m-1} \rightarrow 2^{2 m-2}+2^{m} \text {. }
$$

Note that this last term is a power of two if and only if $2 m-2=m$. This implies that $m$ must be equal to 2 . When $m=2$ and $a_{1}=2^{\ell}$ for $\ell \geq 1$ the sequence eventually cycles through $2,8,4,2, \ldots$ When $m=2$ and $a_{1}=1$ the sequence fails as the first terms are $1,5,5 / 2$.

Solution 2: Let $m$ be a positive integer and suppose that $\left\{a_{n}\right\}$ consists only of positive integers. Call a number small if it is smaller than $2^{m}$ and large otherwise. By the recursion,
after a small number we have a large one and after a large one we successively divide by 2 until we get a small one.

First, we note that $\left\{a_{n}\right\}$ is bounded. Indeed, $a_{1}$ turns into a small number after a finite number of steps. After this point, each small number is smaller than $2^{m}$, so each large number is smaller than $2^{2 m}+2^{m}$. Now, since $\left\{a_{n}\right\}$ is bounded and consists only of positive integers, it is eventually periodic. We focus only on the cycle.

Any small number $a_{n}$ in the cycle can be writen as $a / 2$ for $a$ large, so $a_{n} \geq 2^{m-1}$, then $a_{n+1} \geq 2^{2 m-2}+2^{m}=2^{m-2}\left(4+2^{m}\right)$, so we have to divide $a_{n+1}$ at least $m-1$ times by 2 until we get a small number. This means that $a_{n+m}=\left(a_{n}^{2}+2^{m}\right) / 2^{m-1}$, so $2^{m-1} \mid a_{n}^{2}$, and therefore $2^{\lceil(m-1) / 2\rceil} \mid a_{n}$ for any small number $a_{n}$ in the cycle. On the other hand, $a_{n} \leq 2^{m}-1$, so $a_{n+1} \leq 2^{2 m}-2^{m+1}+1+2^{m} \leq 2^{m}\left(2^{m}-1\right)$, so we have to divide $a_{n+1}$ at most $m$ times by two until we get a small number. This means that after $a_{n}$, the next small number is either $N=a_{m+n}=\left(a_{n}^{2} / 2^{m-1}\right)+2$ or $a_{m+n+1}=N / 2$. In any case, $2^{\lceil(m-1) / 2\rceil}$ divides $N$.

If $m$ is odd, then $x^{2} \equiv-2\left(\bmod 2^{\lceil(m-1) / 2\rceil}\right)$ has a solution $x=a_{n} / 2^{(m-1) / 2}$. If $(m-1) / 2 \geq$ $2 \Longleftrightarrow m \geq 5$ then $x^{2} \equiv-2(\bmod 4)$, which has no solution. So if $m$ is odd, then $m \leq 3$.

If $m$ is even, then $2^{m-1}\left|a_{n}^{2} \Longrightarrow 2^{\lceil(m-1) / 2\rceil}\right| a_{n} \Longleftrightarrow 2^{m / 2} \mid a_{n}$. Then if $a_{n}=2^{m / 2} x$, $2 x^{2} \equiv-2\left(\bmod 2^{m / 2}\right) \Longleftrightarrow x^{2} \equiv-1\left(\bmod 2^{(m / 2)-1}\right)$, which is not possible for $m \geq 6$. So if $m$ is even, then $m \leq 4$.

The cases $m=1,2,3,4$ are handed manually, checking the possible small numbers in the cycle, which have to be in the interval $\left[2^{m-1}, 2^{m}\right)$ and be divisible by $2^{\lceil(m-1) / 2\rceil}$ :
- For $m=1$, the only small number is 1 , which leads to 5 , then $5 / 2$.
- For $m=2$, the only eligible small number is 2 , which gives the cycle $(2,8,4)$. The only way to get to 2 is by dividing 4 by 2 , so the starting numbers greater than 2 are all numbers that lead to 4 , which are the powers of 2 .
- For $m=3$, the eligible small numbers are 4 and 6 ; we then obtain $4,24,12,6,44,22,11,11 / 2$.
- For $m=4$, the eligible small numbers are 8 and 12 ; we then obtain $8,80,40,20,10, \ldots$ or $12,160,80,40,20,10, \ldots$, but in either case 10 is not an elegible small number.