Exercise 6. Let $a \geqslant 2$ and $d \geqslant 2$ be two integers that are coprime. We set $x_{1}=1$; then, for all integers $k \geqslant 1$, we set $x_{k+1}=x_{k} / a$ if $a$ divides $x_{k}$, and $x_{k+1}=x_{k}+d$ otherwise.

Find, in terms of $a$ and $d$, the integer $\ell$ maximal for which $a^{\ell}$ divides one of the terms $x_{1}, x_{2}, x_{3}, \ldots$
Solution to Exercise 6 For any integer $n \geq 1$, let $f(n)$ be the smallest integer such that $a f(n) \geq n$ and $a f(n) \equiv n(\bmod d)$, and let $\delta(n)=(a f(n)-n) / d$. By construction, if we have a term $x_{k}=n$ of the sequence, the following terms of the sequence will be $x_{k+1}=n+d, x_{k+2}=n+2 d, \ldots$, $x_{k+\delta(n)}=n+\delta(n) d=a f(n)$, and then $x_{k+\delta(n)+1}=f(n)$.

Moreover, none of the terms $x_{k+1}, \ldots, x_{k+\delta(n)-1}$ is divisible by $a$, but $x_{k+\delta(n)}=a f(n)$ is. Consequently, if we set $y_{0}=1$ and then $y_{k+1}=f\left(y_{k}\right)$ for all $k \geq 0$, it is a matter of finding the integer $\ell$ maximal for which $a^{\ell-1}$ divides one of the terms $y_{1}, y_{2}, y_{3}, \ldots$

By construction, we know that $\delta(n) \leq a-1$. Therefore, if $n \leq d$, we also know that $f(n) \leq (n+(a-1) d) / a \leq d$. An immediate induction then demonstrates that $1 \leq y_{k} \leq d$ for all integers $k \geq 0$.

Finally, we note that $f(n) \equiv n / a(\bmod d)$, which means, for all integers $k \geq 0$, that $y_{k}$ is the unique integer between 1 and $d$ such that $y_{k} \equiv a^{-k}(\bmod d)$. In particular, if we denote $\omega$ the multiplicative order of $a$ modulo $d$, and if we set $\kappa=\left\lfloor\log _{a}(d)\right\rfloor$, we know that $y_{\omega-\kappa}=a^{\kappa}$. Conversely, since $a^{\kappa+1}>d$, no term $y_{k}$ is divisible by $a^{\kappa+1}$.

We conclude that $\ell=\kappa+1$, that is, $\ell$ is the unique integer for which $d<a^{\ell}<a d$.

Grader's Comment The exercise is quite well done. To solve such an exercise, the first thing to do is to run multiple tests for values of $a$ and $d$ to intuit the correct value. Here, one could observe that the sequence is bounded: finding an explicit bound, whether it be $a \times d$ or $a^{\ell+1}$, and proving it by induction, for example, by showing that the inequality holds each time we divide by $a$. Once such a bound is found, it must be exploited: what inequality does it allow us to prove about the largest $k$ such that $a^{k}$ divides a term of the sequence?

Once this is done, many tried to show that the sequence is periodic. Indeed, it takes a finite number of values, so it takes at least two of the same value. However, be careful, this does not imply periodicity: the sequence defined by $u_{0}=0$ and $u_{n+1}=$ $f\left(u_{n}\right)$, where $f(x)=2 x(2-x)$ satisfies $u_{0}=0$ then $u_{1}=2, u_{2}=2, u_{3}=1, \ldots$ It is ultimately periodic with a period of 2 but is not periodic, as only one of its terms is 0. From the fact that $x_{n+1}$ is defined solely in terms of $x_{n}$ and the fact that the sequence $\left(x_{n}\right)$ takes only a finite number of values, we can only deduce that it is ultimately periodic. To show that it was periodic, it was necessary to prove that if $x_{k}=x_{j}$ with $k, j \geq 1$, then $x_{k-1}=x_{j-1}$. Once periodicity was marked, it was enough to look at a term different from $x_{n}$ that is 1, and to trace back the steps to find a power equal to $a^{\ell+1}$.