Let $a>1$ be a positive integer, and let $d>1$ be a positive integer coprime to $a$. Let $x_{1}=1$ and, for $k \geqslant 1$, define  
$$ x_{k+1}= \begin{cases}x_{k}+d & \text { if } a \text { doesn't divide } x_{k} \\ x_{k} / a & \text { if } a \text { divides } x_{k}\end{cases} $$  
Find the greatest positive integer $n$ for which there exists an index $k$ such that $x_{k}$ is divisible by $a^{n}$. (Croatia)  
Answer: $n$ is the exponent with $d<a^{n}<a d$.
By trivial induction, $x_{k}$ is coprime to $d$. By induction and the fact that there can be at most $a-1$ consecutive increasing terms in the sequence, it also holds that $x_{k}<d a$ if $x_{k}=x_{k-1}+d$ and that $x_{k}<d$ if $x_{k}=\frac{x_{k-1}}{a}$ or $k=1$. This gives the upper bound on the exponent. This implies that the sequence is (eventually) periodic, and that both increasing and decreasing steps happen infinitely many times. Let $a^{-k}$ be the multiplicative inverse of $a^{k}$ modulo $d$. The sequence contains elements congruent to $1, a^{-1}, a^{-2}, \ldots$ modulo $d$. Let $x_{k_{0}}$ the first element such that $x_{k_{0}} \equiv a^{-n}(\bmod d)$. We have either $k_{0}=1$ or $x_{k_{0}}=$ $x_{k_{0}-1} / a$; in both cases $x_{k_{0}}<d<a^{n}<d a$ and therefore 
$$ x_{k_{0}} \in\left\{a^{n}-d, a^{n}-2 d, \ldots, a^{n}-(a-1) d\right\} $$
In this set no element is divisible by $a$, so therefore the sequence will visit the value $a^{n}$ in the next $a-1$ steps.