Let \(a > 1\) be a positive integer and \(d > 1\) be a positive integer coprime to \(a\). Let \(x_1=1\), and for \(k\geq 1\), define
\[x_{k+1} = \begin{cases} x_k + d &\text{if } a \text{ does not divide } x_k \\ x_k/a & \text{if } a \text{ divides } x_k \end{cases}\]
Find, in terms of \(a\) and \(d\), the greatest positive integer \(n\) for which there exists an index \(k\) such that \(x_k\) is divisible by \(a^n\).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.