Periodic sequence problem

Question

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?

Answer 1

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.

Answer 2

Put $p=661=1983/3$ and for each natural $i$ put $b_i\equiv a_i/3 \pmod p$. Then $b_1\equiv 1\pmod p $ and $b_{i-1}=2 b_i\pmod p$ for each $i>1$. Counting $\{b_i\}$ backwards from sufficiently large $i$, we see that its period $N$ is the smallest integer $n$ such that $2^n\equiv 1\pmod p$. Since $p$ is prime, by the Fermat little theorem, $2^{p-1}\equiv 1\pmod p$, so $N|p-1=2^2\cdot 3\cdot 5\cdot 11$. So to show that $N=p-1$ it suffices to check that $2^n\not\equiv 1\pmod p$ for each $n\in \{(p-1)/2, (p-1)/3, (p-1)/5, (p-1)/11\}$. Calculating modulo $p$, we see that

$2^{11}\equiv 2048\equiv 65$, $65^3\equiv 310$, $65^5\equiv 309$.

$2^{(p-1)/2}-1\equiv 2^{330}-1\equiv 65^{30}-1\equiv (65^{15}+1) (65^{15}-1)$,

$65^{15}+1\equiv (65^5+1)(65^5(65^5-1)+1) \equiv 310\cdot (309\cdot 308+1)\not\equiv 0$,

$65^{15}-1\equiv (65^5-1)(65^5(65^5+1)+1) \equiv 308\cdot (309\cdot 310+1)\not\equiv 0$.

$2^{(p-1)/3}-1\equiv 2^{220}-1\equiv 65^{20}-1\equiv (65^{10}+1) (65^5+1) (65^5-1),$

$65^{10}+1\equiv 309^2+1\not\equiv 0.$

$2^{(p-1)/5}-1\equiv 2^{132}-1\equiv 65^{12}-1\equiv (65^6+1) (65^3+1) (65^3-1),$

$65^6+1\equiv 310^2+1\not\equiv 0.$

$2^{(p-1)/11}-1\equiv 2^{60}-1\equiv (2^{30}+1)(2^{15}+1) (2^{15}-1),$

$2^{15}\equiv 2^{11}\cdot 2^4 \equiv 65\cdot 16\equiv 379\not\equiv \pm 1,$

$2^{30}+1\equiv (2^{15})^2+1\equiv 379^2+1\not\equiv 0.$