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\).Like in the first solution, \(x_{k}\) is relatively prime to \(d\) and \(x_{k}<a d\) for all \(k\).
We wish to prove that there are \(n\) consecutive decreasing indices. Let \(m_{0}=0\) and \(m_{k}\) be the \(k\)-th smallest decreasing index (an index \(k\) is decreasing if \(x_{k}=x_{k-1} / a\) ) and define a sequence \(\left(y_{k}\right)_{k}=\left(x_{m_{k}}\right)_{k}\), i.e. the subsequence consisting only of elements with decreasing indices. For each \(k \geqslant 1\) we can write
\[y_{k+1}=\frac{y_{k}+z_{k} d}{a}\]
for some \(z_{k} \in{0,1, \ldots, a-1}\), where \(z_{k}=0\) if and only if \(y_{k}\) and \(y_{k+1}\) are consecutive elements in the original sequence. Then\[y_{k}=\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{k-1} a^{k-1}\right) d}{a^{k}}\]
because \(y_{k}\) is bounded the sequence is (eventually) periodic. Consider some \(y_{u}=y_{u+v}\) where \(v \geqslant 1\). We can write\[y_{u}=\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{u-1} a^{u-1}\right) d}{a^{u}}\]
and\[y_{u+v}=\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{u+v-1} a^{u+v-1}\right) d}{a^{u+v}}\]
and so\[\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{u+v-1} a^{u+v-1}\right) d}{a^{u+v}}=\frac{1+\left(z_{0}+z_{1} a+\cdots+z_{u-1} a^{u-1}\right) d}{a^{u}}\]
Rearranging gives\[\frac{a^{v}-1}{d}=z_{0}+z_{1} a+\cdots+z_{v-1} a^{v-1}+\left(z_{v}-z_{0}\right) a^{v}+\cdots+\left(z_{u+v-1}-z_{u-1}\right) a^{u+v-1}\]
Since \(d>a^{n} / a=a^{n-1}\) the LHS is strictly less than \(a^{v-n}\). This implies that on the RHS, the coefficients of \(a^{v-n}, a^{v-n+1}, \ldots\) must all be zero, i.e. \(z_{v-n}=z_{v-n+1}=\cdots=z_{v-1}=0\). This implies that there are \(n\) consecutive decreasing indices in the original sequence.