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}-1<c_{i}$. This contradicts the minimality of $c_{i}$.

Lemma 2. The sequence $b_{1}, b_{2}, \ldots$ is nondecreasing.

Proof. If $a_{i} \geq 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^{2 c_{i}}+2^{m}$$
and we have the following cases:
- If $2 c_{i}>m$, 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}<m$, then $a_{i+1}=2^{2 c_{i}}\left(b_{i}^{2}+2^{m-2 c_{i}}\right)$, so $b_{i+1}=b_{i}^{2}+2^{m-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}$$
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$.

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^{2 m}+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} \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 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, \ldots$ or $12,160,80,40,20,10, \ldots$, but in either case 10 is not an eligible small number.