APMO

Suppose that for integers $m$ and $a_1$ all the terms of the sequence are integers. For each $i\ge 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,\dots$ 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\ge 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-1<c_i$. This contradicts the minimality of $c_i$.

Lemma 2. The sequence $b_1,b_2,\dots$ is nondecreasing.

Proof. If $a_i\ge 2^m$, then $a_{i+1}=a_i/2$ and thus $b_{i+1}=b_i$. On the other hand, if $a_i<2^m$, then $$a_{i+1}=a_i^2+2^m=b_i^2{2}^{2c_i}+2^m$$ and we have the following cases: - If $2c_i>m$, then $a_{i+1}=2^m\left(b_i^2{2}^{2c_i-m}+1\right)$, so $b_{i+1}=b_i^2{2}^{2c_i-m}+1>b_i$. - If $2c_i<m$, then $a_{i+1}=2^{2c_i}\left(b_i^2+2^{m-2c_i}\right)$, so $b_{i+1}=b_i^2+2^{m-2c_i}>b_i$. - If $2c_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\ge b_i$ since $b_i^2+1\equiv 2(\mathrm{mod}4)$.

By combining these two lemmas we obtain that the sequence $b_1,b_2,\dots$ is eventually constant. Fix an index $j$ such that $b_k=b_j$ for all $k\ge j$. Since $a_n$ descends to $a_n/2$ whenever $a_n\ge 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 $2c_i=m$ and $b_{i+1}=b_i=1$. By Lemma 2, the sequence $b_1,b_2,\dots$ is constantly 1 and thus $a_1,a_2,\dots$ are all powers of two. Tracing the sequence starting from $a_i=2^{c_i}=2^{m/2}<2^m$, $$2^{m/2}\to 2^{m+1}\to 2^m\to 2^{m-1}\to 2^{2m-2}+2^m$$ Note that this last term is a power of two if and only if $2m-2=m$. This implies that $m$ must be equal to 2. When $m=2$ and $a_1=2^{\ell }$ for $\ell \ge 1$ the sequence eventually cycles through $2,8,4,2,\dots$ When $m=2$ and $a_1=1$ the sequence fails as the first terms are $1,5,5/2$.

---

Alternative solution.

Let $m$ be a positive integer and suppose that $\{a_n\}$ 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 $\{a_n\}$ 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^{2m}+2^m$. Now, since $\{a_n\}$ 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 written as $a/2$ for $a$ large, so $a_n\ge 2^{m-1}$, then $a_{n+1}\ge 2^{2m-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\le 2^m-1$, so $a_{n+1}\le 2^{2m}-2^{m+1}+1+2^m\le 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(\mathrm{mod}{2}^{\lceil (m-1)/2\rceil }\right)$ has a solution $x=a_n/2^{(m-1)/2}$. If $(m-1)/2\ge 2⟺m\ge 5$ then $x^2\equiv -2(\mathrm{mod}4)$, which has no solution. So if $m$ is odd, then $m\le 3$.

If $m$ is even, then $2^{m-1}\left|a_n^2⟹2^{\lceil (m-1)/2\rceil }\right|a_n⟺2^{m/2}\mid a_n$. Then if $a_n=2^{m/2}x$, $2x^2\equiv -2\left(\mathrm{mod}{2}^{m/2}\right)⟺x^2\equiv -1\left(\mathrm{mod}{2}^{(m/2)-1}\right)$, which is not possible for $m\ge 6$. So if $m$ is even, then $m\le 4$.

The cases $m=1,2,3,4$ are handled manually, checking the possible small numbers in the cycle, which have to be in the interval $[2^{m-1},2^m)$ and be divisible by $2^{[(m-1)/2]}$: - 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,\dots$ or $12,160,80,40,20,10,\dots$, but in either case 10 is not an eligible small number.