Problem 1801

$n = \max\{m: am < ad\}$; note that this means $a^{n+1} > ad \Rightarrow a^n > d$.

**Solution 1. By induction, $x_k$ is coprime to $d$.** Moreover, note that $x_k$ can increase for at most $a-1$ consecutive terms, so by induction
$$\begin{cases} x_k < da & \text{if } x_k = x_{k-1} + d, \\ x_k < d & \text{if } x_k = x_{k-1}/a \text{ or } k = 1. \end{cases} \quad (1)$$
This implies $a^n < da$. This gives $n \le \max\{m: am < ad\}$.

We now prove that this upper bound indeed satisfies the requirement of the problem. Note that satisfying (1) also means that the sequence $x_k$ must eventually be periodic after some term. Let $a^{-k}$ denote the multiplicative inverse of $a^k$ modulo $d$; then $x_k$ must include $1, a^{-1}, a^{-2}, \dots, a^k \text{ mod } d$, which is equivalent to including $1, a, a^2, \dots \text{ mod } d$. Let $x_\ell$ be the first term congruent to $a^n$; then $\ell = 1$ or $x_\ell = x_{\ell-1}/a$ (otherwise $x_\ell = x_{\ell-1} + d \Rightarrow x_{\ell-1} \equiv a^n$, a contradiction.) In either case, by (1), we have $x_\ell < d < a^n < da$, and hence
$$x_\ell \in \{a^n - d, a^n - 2d, \dots, a^n - (a-1)d\},$$
and none of the numbers in the set on the right is divisible by $a$, so the sequence must reach the value $a^n$ within $a-1$ terms after $x_\ell$.

**Solution 2. As in Solution 1, $x_k$ is coprime to $d$ and $x_k < ad$.** Let
$$S = \{x \in \mathbb{Z}_{>0} : 0 < x < ad, \gcd(x, d) = 1\},$$
and consider $f: S \to S$
$$f(x) = \begin{cases} x+d & \text{if } a \nmid x, \\ x/a & \text{if } a \mid x. \end{cases}$$
Then $x_1 = 1$ and $x_{k+1} = f(x_k)$.

Let us prove that the above recursion is invertible. Suppose that $f(x) = y$ for some pair $x, y \in S$:

- If $y > d$, then necessarily $f(x) = x + d$, so $y - d = x \in S$ and $ay \notin S$;
- If $y < d$, then necessarily $f(x) = x/a$, so $ay = x \in S$ and $y - d \notin S$.

This shows that $f$ is a permutation of $S$, with inverse
$$f^{-1}(y) = \begin{cases} y - d & \text{if } y > d, \\ a \times y & \text{if } y < d. \end{cases}$$

Now, since $f$ is a permutation of $S$, it must be periodic, so there are infinitely many terms equal to 1. Take $\ell$ sufficiently large so that $x_{\ell} = 1$; then we have
$$x_{\ell} = 1, \quad x_{\ell-1} = f^{-1}(x_{\ell}) = a, \dots, \quad x_{\ell-n} = a^n.$$