Answer: all $m>1$ that are not a power of $2$. Case 1: $m$ has a prime divisor $r > 2$. Suppose that for all $k \ge N$, $a_k$ is purely periodic with period $v$. We can find $u\ge N$ such that $a_u\not \equiv 0,1 \mod r$. Otherwise every term $a_k$ would be equivalent to $0,1 \mod r$. However $a_k \equiv 0 \mod r \Rightarrow a_{k+1} \equiv 1 \mod r \Rightarrow a_{k+2} \equiv 2 \mod r$, and since $r>2$ we have a contradiction. Let $\varphi(r)$ be the smallest positive integer such that $a_u^{\varphi(r)}\equiv 1 \mod r$. We have $\varphi(r)>1$ because $a_u\not \equiv 0,1$. We are given that $a_{u+1}\equiv a_{u}^{b_{u}} + 1 \mod m$ and therefore $a_{u+1}\equiv a_{u}^{b_{u+vt}} + 1 \mod m$ for all $t \in \mathbb{N}_0$ because $a_k$ has period $v$. Let $w=u+vt$ for some $t$ and suppose wlog that $b_u < b_w$. Then $a_u^{b_u}+1 \equiv a_u^{b_{w}} +1 \mod m \Rightarrow a_u^{b_u}(a_u^{b_w-b_u} - 1) \equiv 0 \mod m$. Since $r\not | a_u$ we have $a_u^{b_w-b_u}-1 \equiv 0 \mod r$. So $b_{w} \equiv b_u \mod \varphi(r)$. Therefore $b_{u} \equiv b_{u+vt} \mod \varphi(r)$ for all $t\in \mathbb{N}$. Since $2\le \varphi(r) \le m-1$ we have found a purely periodic subsequence of $\{b_n\}_{n \ge 1}$ that meets the condition. Case 2: $m=2^n$ Let $\{b_i\}_{i\ge 1}$ be defined such that $b_1=n+1$, then the next two values are $n+2$, the next three values are $n+3$, and in general the next $k$ terms are $n+k$. This sequence has no periodic subsequence $\mod q$ for any $q$ because any subsequence eventually contains arbitrarily long constant strings at every value $\{0,1,2,...,q-1\}$. However if we let $a_1=1$ then by induction $a_{2k-1}\equiv 1 \mod 2^n$ and $a_{2k}\equiv 2 \mod 2^n$ for all $k \in \mathbb{N}$, which is certainly periodic. So the claim is not true for $m=2^n$ The proof is complete $\square$

ocha wrote: Answer: Case 2: $m=2^n$ Let $\{b_i\}_{i\ge 1}$ be defined such that $b_1=n+1$, then the next two values are $n+2$, the next three values are $n+3$, and in general the next $k$ terms are $n+k$. This sequence has no periodic subsequence $\mod q$ for any $q$ because any subsequence eventually contains arbitrarily long constant strings at every value $\{0,1,2,...,q-1\}$. However if we let $a_1=1$ then by induction $a_{2k-1}=1$ and $a_{2k}=2$ for all $k \in \mathbb{N}$, which is certainly periodic. So the claim is not true for $m=2^n$ The proof is complete $\square$ How did you your induction; $2^{b_n}+1=1$ can't where $a_n=2,a_{n+1}=1$ like you use ($n$ is even)

Sorry I meant $a_{2k-1} \equiv 1 \mod 2^n$ and $a_{2k} \equiv 2 \mod 2^n$, so $a_k$ is periodic $\mod m$