Periodic sequence problem Given sequence $a_n$ defined such that $a_1=3$, $a_{n+1}=\begin{cases}\frac{a_n}{2},\quad 2\mid a_n\\ \frac{a_n+1983}{2},\quad 2\nmid a_n\end{cases}$. Then prove that the sequence $a_n$ is periodic and find the period.
It's easy to prove that $0<a_n<1983$ by induction. By pigeonhole principle, there exist $i,j$ such that $a_i=a_j\implies a_{i+1}=a_{j+1}$. By induction, we can prove $a_{i+k}=a_{j+k},\forall k\in\mathbb{N}$. Otherwise, $a_n\begin{cases}2a_{n+1}, \quad a_{n+1}\le 991\\ 2a_{n+1}-1983, \quad a_{n+1}\ge 992\end{cases}$. So we can prove also $a_{i-k}=a_{j-k} $ for $min(i,j)>k, \forall k\in\mathbb{N}$. So it's periodic. But I can't find the period. In my opinion, the period is $660$. Because $3\mid a_n$ and $0<a_n<1983$. But I can't prove $\forall k, \exists i$ such that $a_i=3k$, Can anyone help me?
 A: As you've noticed, since $3\mid a_1$ and $3\mid 1983$, it follows that $3\mid a_n$ for all $n$. This allows us to simplify the problem by considering the associated sequence defined by $b_n = a_n/3$. We can easily prove by induction that we have $1 \le b_n \le 660$ for all $n$. Since the admissible range of values for $b_n$ is finite, the sequence must be eventually periodic.
Your conjecture that the period is $660$ is in fact true. Showing that the period is $660$ will show that the sequence is not just eventually periodic, but fully periodic (alternatively, as you've noted, this follows from the fact that $b_n$ uniquely determines $b_{n-1}$). The conjecture that the period is $660$, together with the fact that $1 \le b_n \le 660$, motivates looking at the values of the sequence modulo $661$.
Let $[k]$ denote the remainder of $k\in \mathbb{Z}$ modulo $661$, i.e., the unique integer $0 \le [k] < 661$ such that $[k] \equiv k \pmod{661}$. Since $1 \le b_n < 661$, it follows that $b_n = [b_n]$ for all $n\in \mathbb{N}$.
Lemma 1: Let $m \in \mathbb{Z}$ be an even integer. Then $[m/2] = [331m]$.
Proof: Note that $2$ is a unit in $\mathbb{Z}/661\mathbb{Z}$. Indeed, we have $2^{-1} \equiv 331 \pmod{661}$. Therefore we have
$$331m \equiv 331 \cdot \left[2\cdot \left(\frac{m}{2}\right)\right] \equiv [331 \cdot 2]\left(\frac{m}{2}\right)\equiv \frac{m}{2} \pmod{661}.$$
It follows that $[m/2] = [331m]$. $\square$
Lemma 2: For all $n\ge 1$, we have $b_n = [331^{(n-1)}]$.
Proof: Consider the defining recursion
$$b_{n+1} = \begin{cases}b_n/2 & 2 \mid b_n,\\ (b_n + 661)/2 & 2\not\mid b_n.\end{cases}$$
In the first case, we have
$$b_{n+1} = [b_{n+1}] = [b_n/2] = [331b_n].$$
In the second case, we have
$$b_{n+1} = [b_{n+1}] = [(b_n + 661)/2] = [331(b_n + 661)] = [331b_n].$$
In either case, we have $b_{n+1} = [331b_n]$. Starting with $b_1 = 1$, it follows that $b_n = [331^{(n-1)}]$. $\square$
The period of the sequence is therefore the order of $331$ mod $661$. The result then follows by noting $661$ is prime, so that $(\mathbb{Z}/661\mathbb{Z})^{\times} \cong \mathbb{Z}_{660}$ is cyclic, and moreover that $331$ (or equivalently, $2$) is a primitive root modulo $661$. This last fact can be verified with a quick (albeit tedious) calculation.
