# Find values of $a$ for which the function is periodic.

Given a positive integer $$m$$ consider the sequence $$\{a_n\}$$ of positive integers defined by the initial term $$a_0=a$$ and the recurrence relation

$$a_{n+1} = a_n/2$$ if $$a_n$$ is even; $$a_n+m$$, if $$a_n$$ is odd.

Find all values of $$a$$ for which the sequence is periodic.

Fact 1: If there are two distinct $$k_1$$ and $$k_2$$ s.t. $$a_{k_1}=a_{k_2}$$ then the sequence repeats.

If $$m$$ is odd (the crux of the problem) then each $$a_k$$ is no larger than $$a_1 + 3m$$ [make sure you see why or check the proof below; essentially you get to add by $$m$$ only once before you have to divide by 2]. As each $$a_k$$ is positive it follows that $$a_k \in \{1,2,\ldots, a_1+3m\}$$ for all $$k$$. Therefore it follows from Fact 1 that the sequence repeats.

If $$m$$ is even and positive then let $$i_0$$ be the smallest integer such that $$a_12^{-i_0}$$ is no longer even--or equivalently $$2^{-i_0}a_1$$ is odd. Then $$a_2 = a_12^{-1}$$, $$\ldots ,$$ $$a_{i_0+1} = 2^{-i_0}a_1$$, while $$a_{i_0+1+j} = a_12^{-i_0} + jm$$ for each nonnegative integer $$j$$ [make sure you see why; note that $$a_{i_0+j+1} = a_12^{-i_0} + jm$$ is an odd integer as $$a_12^{-i_0}$$ is odd and $$m$$ is even]. So the function is not periodic.

So for a positive integer $$m$$, the function is periodic iff $$m$$ is odd, no matter what positive integer $$a_1$$ is.

[If $$m$$ is 0 and $$a_1$$ is odd then all of the $$a_n$$s are $$a_1$$. If $$m=0$$ and $$a_1$$ is even then letting $$i_0$$ be the smallest integer s.t. $$a_12^{-i_0}$$ is odd, then $$a_n=a_12^{-i_0}$$ for all $$n > i_0$$.]

Proof that $$a_k< a_1+3m$$ for all $$k$$ if $$m$$ is odd: We first show that $$a_k < a_1+2m$$ if $$a_k$$ is odd, by induction on $$k$$. Let us assume that $$a_{k_0} < a_1+2m$$ and that $$a_{k_0}$$ is odd. Then $$a_{k_0+1}=a_{k_0}+m$$ is even [as $$m$$ is odd] and is no greater than $$a_1+3m$$. Then $$a_{k_0+2} = a_{k_0+1}/2$$ is no greater than $$a_1/2 + 3m/2 < a_1+2m$$. So indeed, $$a_k < a_1+2m$$ if $$a_k$$ is odd.

Now we claim that $$a_k < a_1+3m$$ if $$a_k$$ is even. Indeed, let us use induction on $$k$$. If $$a_{k-1}$$ is even then by induction hypthesis $$a_{k-1} < a_1+3m$$ and $$a_k = a_{k-1}/2 < a_{k-1}$$ so indeed, $$a_k < a_1+3m$$ as well. If $$a_{k-1}$$ is odd then by the previous paragraph $$a_{k-1} < a_1+2m$$, which implies $$a_k < a_1+3m$$. Thus indeed, $$a_k < a_1+3m$$ if $$a_k$$ is even.

So $$a_k < a_1+2m$$ if $$a_k$$ is odd and $$a_k < a_1+3m$$ if $$a_k$$ is even, so the $$a_k$$s are indeed bounded.