An eventually periodic sequence

The proof turned out to be tediously long. So, bear with me.

First, we make the following claim:

The sequence $\{c_n\}_{n\ge 0}$ with $c_0\in [0,1]$ is eventually periodic iff $c_0$ is rational.

Proof:

if part: Let $c_0$ be a rational number in $[0,1]$ . For $c_0=0,1$ , the sequence becomes $\{1,0,1,0,\cdots\}$ and $\{0,1,0,1,\cdots\}$ respectively, which is clearly periodic with period $2$ . So now on we consider the case $0<c_0<1$ . Now we make the following simple observation, which can be easily verified by direct computation:

If $c_0<1/2^{k}$ , for some $k (1\le k\le 2)$ , $c_n=2^n c_0,\ 1\le n\le k$ .

Note that $c_k=2^kc_0<1$ . If $c_k\in (0,1/2)$ , then from the recursion, we have $c_{k+1}=2c_k\in (0,1)$ ; otherwise, $c_{k+1}=2(1-c_k)\in (0,1)$ since in this case $c_k\in (1/2,1)$ . So, in any case the sequence is bounded, and obviously positive, and hence has positive limit points. Note that this observation is valid for any $c_0\in (0,1)$ .

Since at each iteration $c_{k+1}$ is of the form $2a_k\pm 2c_k$ where $a_k$ is a constant number in $\{0,-2\}$ , $c_k$ is always a rational number if $c_0$ is rational and is always in $0,1$ . Then, at some iteration $k$ , let, $\exists p,q\in \mathbb{N},\ p< q, \gcd(p,q)=1$ , such that $c_k=\frac{p}{q}$ . Also, note that because of the previous observations, if $c_0=\frac{1}{2^m}$ for some $m$ , then, $c_m=1$ , and then onwards it is the $1,0,1,0,\cdots$ sequence. So we take $c_0\ne \frac{1}{2^k}$ . Now we consider two cases,

Case 1: $p<q/2$ : Then $c_{k+1}=\frac{2p}{q}$ . If $2|q$ , then, $c_{k+1}=\frac{p}{(q/2)}$ , where $\gcd(p,q/2)=1$ , thus we have $c_{k+1}=\frac{p'}{q'}$ , with $p'=p$ , and $q'=q/2$ , with $q'$ having one less power of $2$ in its factorization. If $q$ is odd, then we have $c_{k+1}=\frac{p'}{q'}$ with $p'=2p,\ q'=q,\ p'<q', \gcd(p',q')=1$ .

Case 2: $q/2\le p<q$ : In this case $c_{k+1}=\frac{2(q-p)}{q}$ . If $q/2=p$ , the sequence becomes the $1,0,1,0,\cdots$ sequence from $k+1$ onwards. Otherwise, If $2|q$ , then, $c_{k+1}=\frac{q-p}{q/2}$ , and note that $\gcd(q-p,q/2)=1$ . Also, $q-p< q/2$ , and note that $q-p\ne p$ Thus we can write $c_{k+1}=\frac{p'}{q'}$ , where $p'=q-p,\ q'=q/2, \gcd(p',q')=1,\ p'<q'$ . If $q$ is odd then $c_{k+1}=\frac{p'}{q'},\ p'=2(q-p),\ q'=q,\ p'<q', \gcd(p',q')=1$ .

From the above two cases we can see that if $2^l|q$ , after $l$ iterations we have $c_{l+k}=\frac{p'}{q'}$ where both $p',q'$ are odd. Let us assume that $m$ is the iteration number where $q'$ becomes odd for the first time. In the next iterations, we see that the $c_k$ has the form $\frac{p'}{q'}$ , where the denominator remains the same $q'$ , whereas, the numerator $p'$ changes and takes distinct values. But $p'$ can take only $\phi(q')$ number of values, and hence $\exists$ some iteration $m+j$ , $1\le j\le \phi(q')$ , such that the value of $p'$ after that iterations must coincide with an earlier value, i.e. $\exists$ some $i\le m$ such that $c_i=c_{m+j}$ . Thus, the sequence becomes eventually periodic with period $\le \phi(q')$ .

only if part: Let $c_0$ be an irrational number in $(0,1)$ . Now, if $c_0\in (1/2,1)$ , $c_1=2(1-c_0)$ , and consequently, $c_n$ is of the form $2a_n\pm n^n c_0$ , for all $n\ge 1$ with $a_n$ integer, [I am not providing a proof for this statement, though I think this is pretty straightforward to proof, maybe by induction]. On the other hand, if $c_0\in (0,1/2)$ , there exists $k\ge 1$ , such that $c_n=2^n c_0, \forall 1\le n\le k$ , and $c_{k+1}=2(1-c_k)$ . Since $c_0$ is irrational, it is not possible to have $c_k=1$ , and thus, $\forall n\ge k+1$ , again we have $c_n$ of the form $2a_n\pm 2^n c_0$ . Thus, if $c_n$ is eventually periodic, we can find some large $m$ (i.e. $m\ge k+1$ ), and some positive integer $N$ such that $c_m=c_{m+N}\implies 2(a_m-a_{m+N})=\pm2^m (2^N\pm 1)c_0$ , which is absurd as LHS is rational, whereas RHS is not. Thus the sequence $\{c_n\}$ cannot be eventually periodic. $\blacksquare$

---

Let us now try to find a way to find the period of the sequence $\{c_n\}_{n\ge 0}$ , when $c_0$ is of the form $c_0=\frac{1}{p}$ , where $p$ is an odd prime. First of all, as discussed earlier, since $p$ is odd, in the evolution of $c_n$ , only the numerator will change and the denominator will remain constant. Thus, it is enough to look at the sequence constituted by the numerators. In the sequel we will denote by $a_n$ the numerator of $c_n$ .

We claim the following:

Let $a_{n+1}=2k,\ n\ge 1$ . Then $a_{n}=\frac{a_{n+1}}{2}$ if $k$ is even and $a_{n}=p-\frac{a_{n+1}}{2}$ , if $k$ is odd

Proof: Observe that if $k$ is even and $a_n=p-\frac{a_{n+1}}{2}=p-k$ , then $a_n$ is odd, which is not possible since every $a_n$ is even for $n\ge 1$ . In a similar fashion, it is easy to see that if $k$ is odd, we must have $a_n=p-\frac{a_{n+1}}{2}$ . $\blacksquare$

Here is another claim:

The sequence $\{a_n\}$ is eventually periodic with period $N$ , where $N=\min\{n\ge 1: \ a_{n+1}=2\}$ Proof: Let $N$ be the period and $m$ be defined as $m=\min\{n\ge 0: a_m=a_{m+N}\}$ Note that $m=0$ is not possible, since from the recursion, $a_m$ is even for all $m\ge 1$ , and $a_0=1$ . If $m>1$ , then, from the characterization of $a_{m-1}$ from the last claim, we find that $a_{m-1}=a_{m-1+N}$ which violates the minimality of $m$ . If $m=1$ , however, the characterization in the last claim does not apply, and is the only possible option. Since we know that the sequence has to be eventually periodic, this is the only option. Thus, the claim follows. $\blacksquare$

Finally (Phew..) we claim the following:

The sequence $\{a_n\}_{n\ge 0}$ is eventually periodic with period $\frac{\mathrm{ord}_{p}(2)}{4}(3-(-1)^{\mathrm{ord}_{p}(2)})$ where $\mathrm{ord}_p(2)=\min\{k\ge 1: 2^k\equiv 1(\mod p)\}$

Proof: Since the last claim shows that $a_{N+1}=2$ , we must have $a_N=p-1$ . Then, $a_{N-1}=\frac{p-1}{2}$ , if, $\frac{(p-1)}{2}$ is even, and otherwise, $a_{N-1}=p-\frac{p-1}{2}$ . Continuing in this manner it is not difficult to show that the form of $a_i$ will be either of the following forms $p-\frac{p-\frac{p-\cdots\frac{p-\frac{p-1}{2^{l_0}}}{2^{l_j}}}{2^{l_{j+1}}}}{2^{l_{j+2}}},\quad \frac{p-\frac{p-\frac{p-\cdots\frac{p-\frac{p-1}{2^{l_0}}}{2^{l_k}}}{2^{l_{k+1}}}}{2^{l_{k+2}}}}{2^{l_{k+3}}}$ At the end, we should get $a_0=1$ , which means that we should get the following type of equation: $\frac{p-\frac{p-\frac{p-\cdots\frac{p-\frac{p-1}{2^{l_0}}}{2^{l_k}}}{2^{l_{k+1}}}}{2^{l_{k+2}}}}{2^{l_{k+3}}}=1\\\implies p\left(2^{\sum_{j=0}^{k+2}l_{j}}-2^{\sum_{j=0}^{k+1}l_j}+\cdots s_k \right)= 2^{\sum_{j=0}^{k+3}l_j}+s_k)$ where $s_k=\pm$ . Thus if $p|2^{k}-1$ and $p|2^{l}+1$ , then whichever number is smaller, for that the multiplier of $p$ can be uniquely expressed (Needs to be proven, but seems to be true) in the form of the multiplier of $p$ as shown above, and that representation will then uniquely determine the numbers $a_1,\cdots, \ a_N+1$ . Hence the period must be $k$ if $2^k-1<2^l+1$ , or $l$ if $2^l+1<2^k-1$ [Note that the period is actually the exponent $\sum_{j=0}^{k+3} l_j$ ]. By definition of multiplicative order, we have that $N|\mathrm{ord}_p(2)$ . Now, if the order is odd, then there is no such $l$ such that $2^l+1<2^{\mathrm{ord}_p(2)}-1$ , because otherwise $2l|\mathrm{ord}_p(2)$ which is not possible. So, then period is $\mathrm{ord}_p(2)$ . On the other hand if $\mathrm{ord}_p(2)$ is even, then, $p|2^{\mathrm{ord}_p(2)/2}+1$ , and there is no smaller number of this form that is divisible by $p$ . Hence, then the period is $\mathrm{ord}_p(2)/2$ . Together they prove the claim. $\blacksquare$ (Phew...)

Since here $p=2017$ , $\mathrm{ord}_{2017}(2)=336$ , and hence the period is $336/2=\boxed{168}$ .