The answer is the largest $n$ such that $a^n<ad$. First, we claim that no larger $n$ is possible. It's enough to show that $x_k<ad$ for all $k$. We prove this by induction. The idea is that if we divide by $a$, i.e. if $x_{k+1}=\frac{x_k}{a}$, then $x_{k+1}<d$ by induction. Additionally, because $\gcd(a,d)=1$ there is an $r\in [0,a-1]$ such that $x_{k+1}+rd\equiv 0\pmod{a}$, and because $x_{k+1}+rd<ad$, we never have a $t$ with $x_t\ge ad$. Now I will show that such an $n$ is eventually achievable. We show that we can get an $n$ with $ad>a^n>d$. Notice that modulo $d$, the sequence is $(1,1,\cdots,1,a^{-1},a^{-1},\cdots, a^{-1}, a^{-2}, \cdots, a^{-2}, \cdots)$. This means that $\{x_k\}$ is a complete residue system modulo $d$. Hence eventually the sequence reaches $1$ again. Thus at some point the sequence goes $a^k-d\to a^k\to a^{k-1}\to \cdots\to 1$. Hence we reach a $k$ with $a^k>d$, as wanted.

Let $k = \lfloor \log_a(d) \rfloor + 1$. The answer is $a^k$. Proof of Bound: It is enough to show every element of the sequence is below $ad$. We can strong induct, the base case being obvious. If the most recent operation was dividing, then we are done. Otherwise, AFTSOC we are at $x\geq ad$. However the last time we divided, we must have been below $d$, but obviously we must have saw an element divisible by $a$ somewhere before, since $\gcd(a,d)=1$. Proof that it works: Since the sequence must repeat by Pigeonhole, it is also periodic. We can extend the sequence backwards to find that $a_{-1}=a^1, a_{-2} = a^2, \dots, a_{-k} = a^k$, so we are done. Remark: Seemed somewhat similar to 2003 N1, and the extending backwards argument also worked in that problem.

The answer is $\lfloor \log_{a}d\rfloor+1$. Claim: For all indices $i,$ we have $a_i<ad$. Proof: Use strong induction with base cases easily checkable. Then, assuming true up to $n-1$, we show $a_n<ad$. To do so, consider the last place in the sequence where we divided, ie the last place where $a_i<d$ by the hypothesis. But now we can only add $d$ at most $a-1$ times since if we did it $a$ times, the sequence would loop back mod $a$ and we could divide previously at some point. This means $a_n<d+(a-1)d=ad$ as desired. This claim means given any $a_i=k,$ we can determine the value of $a_{i-1}$, being $ka$ if $k<d$ and $k+d$ otherwise. But also from the claim, the sequence must be periodic, so by what we showed above, if it repeats we can trace the sequence back to $a_1=1$ so $a_1$ must be in the repeat. Then, for any index $j>0$ with $a_j=a_1,$ we know $a_{j-1}=a, a_{j-2}=a^2,$ and so on until $a^k>d$. Thus we will reach $ad>a^k>d$ and taking $\log_a$ of each side gives the result

The answer is the largest perfect power of $a$ less than $ad$. Note that the sequence $x$ consists of adding $d$ until we reach a multiple of $a$, and then dividing by $a$ until we reach a non-multiple of $a$; this repeats over and over again. Using induction, we can show that $x_k$ never exceeds $ad$ for any value $k$, even when it is not a perfect power. We start at the base case of $x_1 = 1$, where we will have to add $d$ at most $a-1$ times before we reach a multiple of $a$. Thus, the first multiple of $a$ we reach will be at most $d(a-1) + 1 < ad$. After dividing by $a$ at least once, our number is definitely less than $d$. Then, the same process repeats; starting from some $x_i < d$, we add $d$ at most $a-1$ times before we reach a multiple of $a$. This multiple of $a$ will be at most $d(a-1) + x_i < ad$, and then we divide by $a$ again, and so on and so on. Now we show that we will actually obtain the largest perfect power of $a$ less than $ad$ at some point in our sequence. Claim: the sequence cycles back to $1$ eventually. Assume otherwise for the sake of contradiction. Our sequence consists of starting at some integer in the range $[1, d)$, and then adding $d$ until we reach a multiple of $a$ which will lie in the range $(d, ad)$. No two multiples of $a$ in the range $(d,ad)$ are themselves separateed by a factor of $a^k$ due to size; therefore, we can correspond every multiple of $a$ in the range $(d,ad)$ to a unique result in the range $[1,d)$ after repeatedly dividing by $a$. All of this is to say, we can uniquely reverse engineer a sequence given any element in the sequence; this implies that we will eventually cycle back to $1$. Now, note that the highest multiple of $a$ we reached just before returning to $1$ is a perfect power of $a$ that lies in the range $(d,ad)$; there is only one such number, which is the largest power of $a$ less than $ad$.

I claim the answer is $\boxed{\lfloor \log_a{d}\rfloor + 1}$. Claim 1: $x_c < ad$ for all c. Proof: Clearly, the result is true for c = 1. Then assume it is true for all $c \leq n $ such that $x_n < d$. Then the proceeding terms we continuously add $d$ to $x_n$ until we reach some $a | x_{n+i}$. Note that since $gcd(a, d) = 1,$ we know that some value in $x_n, x+d_n, x_n + 2d, \cdots, x_n + (a-1)d$ is divisible by $d$. Thus this additive process must terminate before $x_{n+i} \leq x_n + (a-1)d < d + (a-1)d = ad$. Then, $x_{n + i + 1} \leq d$, and this process repeats. Since we have an infinite sequence that and a finite range, the sequence is periodic. Claim 2: the number 1 repeats periodically. Proof: from the first lemma, we can see that if $x_c \leq d$, then $x_{c-1} = ax_c$ and otherwise if $x_c > d$, then $x_{c-1} = x_c - d$. Let $x_p \neq 1$ be the first periodic value. Then all occurrences of $x_{p-1}$ are also periodic, since they are determined as a previous occurrence at every repeat of $x_p$, a contradiction to the minimality of $p$. Thus we must have $p = 1$. Now consider $x_c = 1$ where $c > d+1$. Then $x_{c-1} = a$ and following from that, $x_{c-i} = a^i$ for integers until $i = k$ such that $2^k > d$ and $2^{k-1} \leq d$. so $k = 1 + \lfloor \log_a{d}\rfloor$. Also, note that since $x_c < ad$, we can write $x_c < a\cdot a^{k} = a^{k+1}$, thus the maximum of $v_a(x_k) = 1 + \lfloor \log_a{d}\rfloor$.

ISL 2022 N3. Let $a>1$, $d>1$ be integers such that $\gcd(a, d)=1$. Let $x_1=1$, and for $k\ge 1$, define \[x_{k+1}=\begin{cases}x_k+d, a\nmid x_k\\\frac{x_k}a, a\mid x_k\end{cases}.\]Determine in terms of $a$ and $d$ the greatest positive integer $n$ such that $a^n\mid x_k$ for some $k$. Solution. The greatest such integer $n$ is \[\lfloor\log_ad\rfloor+1\stackrel{\gcd(a, d)=1}{=}\lceil\log_ad\rceil.\]We start from proving that $n\le\lfloor\log_ad\rfloor+1$. Claim 1. $x_k\le ad$ for all $k\in\mathbb Z_+$. Proof. Since $\gcd(a, d)=1$, we have $x_k\equiv 0\pmod a$ for some $k\le a$. Then $x_k\le 1+(a-1)d<ad$. Then $x_{k+1}=\frac{x_k}a\le\frac{1+(a-1)d}a<\frac{1+ad}a=d+\frac1a$, so $x_{k+1}\le d$. Let $\ell$ be the smallest positive integer such that $a\nmid x_{k+\ell}$. Then $x_{k+\ell}\le d$. For the same reason, we have $x_{k+\ell+j}\equiv 0\pmod a$ for some $j\le a-1$. Then $x_{k+\ell+j}\le d+jd=d(j+1)\le ad$. Then $x_{k+\ell+j+1}=\frac{x_{k+\ell+j}}a\le\frac{ad}a=d$. Repeating the same logic completes the proof. Claim 2. $(x_k)$ is periodic. Proof. Since the value of $x_{k+1}$ is solely depending on that of $x_k$ for any $k\in\mathbb Z_+$, it suffices to show that $x_i=x_j$ for some $i\ne j$. However, this is immediate from Claim 1 and the pigeonhole principle. From here we can deduce that $n\le\lfloor\log_ad\rfloor+1$ because otherwise we would have \[n\ge\lfloor\log_ad\rfloor+2=\lfloor\log_ad+2\rfloor>\log_ad+1=\log_a(ad)\implies ad<a^n\mid x_k\le ad,\]which is a contradiction. Next we show that $n=\lfloor\log_ad\rfloor+1$ is actually achievable. Claim 3. $x_k=a^{\lfloor\log_ad\rfloor+1}$ for some $k\in\mathbb Z_+$. Proof. Let $s=\lfloor\log_ad\rfloor$. Then $a^s\le d<a^{s+1}$. By periodicity, we have $x_j=x_1=1$ for some $j>1$. We show that $x_{j-r}=a^r$ for any $1\le r\le s+1$. Note that if $x_{j-1}=x_j-d$ then $x_{j-1}<0$, which is a contradiction. Hence $x_{j-1}=ax_j=a=a^1$. Assume that $x_{j-\alpha}=a^\alpha$ for some $1\le\alpha\le s$. Then if $x_{j-\alpha-1}=x_{j-\alpha}-d$ then $x_{j-\alpha-1}=a^\alpha-d\le a^s-d\le 0$, which is a contradiction. Hence $x_{j-\alpha-1}=ax_{j-\alpha}=a^{\alpha+1}$. Therefore, $x_{j-s-1}=a^{s+1}=a^{\lfloor\log_ad\rfloor+1}$, as desired. By Claim 3 we pick $k$ such that $x_k=a^{\lfloor\log_ad\rfloor+1}$, the proof of achievability is established.

Let the index $k$ be good if $a\mid x_{k-1}$. We define $1$ to be good by default. We claim for all good $k$, $x_k<d$. Indeed, if $k$ is the smallest good index such that $x_k\ge d$ then $x_{k-1}\ge ad$. Let $j$ be the largest good index such that $j<k$ then $x_j<d$. Note that among the numbers \[\{x_j,x_j+d,\dots, x_j+(a-1)d\}\]one of them must be divisible by $a$. However, all of them are smaller than $ad$, contradiction. In particular, this means no value in our sequence can be at least $ad$. Now, let our good indices by $1=k_1<k_2<k_3<\dots$ then we claim that $x_{k_{i+1}}\equiv a^{-1} x_{k_i} \pmod d$. Indeed, let $x_{k_i}=c$ then $x_{k_{i+1}-1}\equiv 0\pmod a$ so $c+d(k_{i+1}-k_i-1)\equiv 0\pmod a$. We have that \[ax_{k_{i+1}}=x_{k_{i+1}-1}\equiv (ca^{-1})a \pmod {ad}\]so $x_{k_{i+1}}\equiv ca^{-1}\pmod d$ as desired. Thus, let $n-1$ be the largest value that ensures $a^{n-1}<d$ then there exists some good index $i$ such that $x_i\equiv a^{n-1}\pmod d$ and therefore $x_{i-1}=a^n$. If $a^{n-1}\ge d$ then $a^n$ is not achievable, so the answer is the described $n$.

Sketch: By playing with small $a$ and $d$, we speculate the answer is $\lceil(log_a(d)\rceil$. We can prove this by first showing there is no term larger than $ad$ in the sequence, and that there exists a sequence with $a^{\lceil(log_a(d)\rceil}$ back-tracking to a $1$.

Fun problem, not-so-different form of the problem appeared on the Croatian Mathematical Olympiad 2011, with the following statement: For a positive integer $d$ the sequence is defined as follows: $a_0 = 1$ $a_{n+1} = \begin{cases} \frac{a_n}{2} &\text{if } a _n\text{ is even} \\ a_n + d &\text{otherwise} \end{cases}$ For which values of $d$ there exists a positive integer $n$ for which $a_n = 1$? here is the link if you want to look it up https://natjecanja.math.hr/wp-content/uploads/2015/02/2011-izborna-rjesenja.pdf

quite EZ as one of the only questions of IMOsl i can handle

Nice Problem! We claim $n=\lceil\log_a d\rceil$ Claim 1: $x_i < ad$

Then by php the sequence is periodic, extend backwards to get the desired.

We claim that the answer is $\lceil log_a d \rceil$. We first show that the sequence cannot go above $ad$, by induction. This is quite simple. Define a new sequence $y_k$ to be every value of $x_k$ that is a multiple of $a$. We proceed by induction on $y_k$. The base case is trivial by CRT. For the induction step, observe that $y_{k+1}$ is the least integer greater than or equal to $\frac{y_k}{a}$ that is $\frac{y_k}{a} \bmod{d}$ and $0 \bmod{a}$. However, because $\frac{y_k}{a}$ is less than or equal to $d$ by the induction hypothesis, there cannot be a positive integer equal to $\frac{y_k}{a} \bmod{d}$ and $0\bmod{a}$ that is less than $\frac{y_k}{a}$, so by CRT we conclude that $y_{k+1} \leq ad$. This completes the proof that the sequence cannot go above $ad$, because if some term goes above $ad$, then the next term in $y_k$ is also above $ad$, contradiction. This proves that no $n > \lceil log_a d \rceil$ works. Showing that $n = \lceil log_a d \rceil$ works is also simple. Define $z_k$ to be the sequence of $y_k \bmod{d}$. Then, it is trivial that $z_k = a^{-k+1} \bmod{d}$. Because $z_k$ is periodic, it must contain $a^n \bmod{d}$. Therefore, there exist $x_k$ which are equal to $a^n \bmod{d}$. Additionally, by CRT, $a^n$ is the only positive integer less than or equal to $ad$ which is $a^n \bmod{d}$ and $0 \bmod{a}$. Hence, if $x_k$ never becomes equal to $a^n$, it will clearly grow greater than $ad$ when it is equal to $a^n \bmod{d}$, a contradiction. Thus, we are done.

In this Number Theory problem, the upper bound is easy to prove using Chinese Remainder Theorem, but the lower bound is more tricky, because one needs to calculate the relationship between the values of $y_{k}$ using remainder modulo k.

We claim that answer is $\lceil\log_a(d)\rceil$. Claim: We have $x_n<ad$ for all $n$. Proof. For any $a\nmid x$ such that $x<ad$, consider the numbers $x,x+d,\ldots,x+(a-1)d$. Since $\gcd(a,d)=1$, this is a complete residue class $\pmod a$. Hence, there is some $1\leq i\leq a-1$ for which $a\mid x+id$. So, if $x_n=x$ then $x_{n+i}=x+id$ and \[x_{n+i+1}=\frac{x+id}a<\frac{ad+id}a<2d\leq ad\]This means that if $a\nmid x_n$ then $x_n<ad$. This also means that if $a\mid x_n$ then either $x_{n-1}=ax_n$ or $x_{n-1}=x_n+d$. Choose $n$ such that $a\nmid x_{n-1}$. Then, $x_n=x_{n-1}+d<(a+1)d$. However, since $a\mid x_n$, this forces $x_n\leq ad$. Suppose possible $x_n=ad$. Then, we see that $x_n$ is eventually just $d, 2d, \ldots, ad$ repeating periodically. Now, note for any $j>1$ and large $n$, if $x_n=jd$ then $x_{n-1}=ajd>ad$ is not possible. So, $d$ divides all terms of sequence. This gives $d\mid x_1=1$ which contradicts $d>1$. $\blacksquare$ So, the answer is (strictly) less than $\log_a(ad)=\log_a(d)+1$. We now show that $\lceil\log_a(d)\rceil$ works. Let $\lceil \log_a(d)\rceil=s$. Then, $a^s<ad<a^{s+1}$. Consider the backtracking $y_{k+1}=y_k-d$ if $y_k>d$ and $y_{k+1}=ay_k$ otherwise. Note that since the sequence is always and bounded above, it means the sequence is periodic. Extending the sequence for negative indices, we get $x_0=a$ and $x_{-1}=a^2$ and finally $x_{1-s}=a^s$. We're done because the sequence is periodic. $\blacksquare$

The answer is the number of digits of $d$ when written in base $a$. Notice that all the terms in the sequence must be smaller than $ad$ as you only need to add $d$ at most $a-1$ times and then you divide by $a$. This proves the upper part of the bound. Now we claim that the sequence is periodic. Notice that the sequence is bounded so it must be eventually periodic. However since the upper bound is $ad$ the sequence can be constructed in reverse so the sequence must be periodic starting from $x_1$. So for some $m>1$ we have $x_m=1$ and working backwards proves the lower part of the bound.

Love these ultra-rigid problems where you completely analyze the sequence and the problem falls apart The answer is $\lceil \log_a d \rceil$. In particular, let $k$ denote this quantity, so $a^{k-1} < d \leq a^k$. Claim. $x_n < ad$ for all $n \geq 1$. Proof. Assume otherwise, and let $n_0$ be the smallest index such that $x_{n_0} \geq ad$. Then, for all $i \leq n_0$ such that $x_i \geq d$, we must have $x_{i-1} = x_i - d$, otherwise $x_{i-1} = ax_i \geq ad$ contradicts minimality of $n_0$. However, we inductively have \[x_{n_0 - i} = x_{n_0} - id \geq (a-i)d \geq d\]for all $0 \leq i \leq a-1$. It follows that one of these $a$ numbers $x_{n_0 - i}$ is a multiple of $a$. But $x_{n_0 - i+1} = x_{n_0-i} + d$ for this $i$, contradicting definition of the sequence. $\blacksquare$ Claim. The sequence $\{x_n\}$ is completely periodic. Proof. As $x_n$ attains finitely many values by the first claim, by Pigeonhole there are $i, j$ with $x_i = x_j$ and thus $x_{i+\ell} = x_{j+\ell}$ for any $\ell \geq 0$, so $\{x_n\}$ is eventually periodic. To see that $\{x_n\}$ is completely periodic, consider any $x_n$. If $x_n \leq d$, then we must have $x_{n-1} = x_n$ as all terms are strictly positive. If $x_n > d$, then if $x_{n-1} = ax_n$, then $x_{n-1} > ad$, which contradicts the first claim. So $x_n$ uniquely fixes $x_{n-1}$ and the result follows. $\blacksquare$ The first claim shows the bound as $ad < a^{k+1}$. Now, the second claim implies that there is an $N$ with $a_N = 1$. Then $a_{N-i} = a^i$ for each $1 \leq i \leq k$ because $a_{N-i + 1} \leq a^{k-1} < d$. In particular, $a_{N-k} = a^k$ satisfies the condition.

Times surely have changed, i remember struggling with this problem on 2023 TST and now i barely took 30 mins on it, it sort of gives me nostalgia to think about it. Claim 1: $x_n<ad$ for all positive integers $n$ Proof: Recall that $\ell, \ell+d, \cdots, \ell+(a-1)d$ is a complete residue system $\pmod a$ for any positive integer $\ell$ since $\gcd(a,d)=1$, so the first terms are $1, d+1, \cdots md+1$ (all of them are $<ad$) and since $m \le a-1$ we get that the next term is some $\ell<d$, but then the same things applies, you get something of the shape $m'd+\ell$ (which is also $<ad$) as the last term before dividing it by $a$ and since $m' \le a-1$ and $\ell \le d-1$ we get that the next term is also $\le d$, so inductively we can never pass above $ad$. Claim 2: We can attain at most the biggest exponent $n$ for which $ad>a^n>d$ Proof: Note that since the sequence is bounded it repeats at some point by Infinite PHP so it is eventually periodic by its definition (in fact we know that if $a_k=\ell<d$ then $a_{k-1}=a \cdot \ell$ and if $a_k>d$ then $a_{k-1}=a_k-d$), so suppose at some point for $s>1$ we have $a_s=1$, then $a_{s-1}=a$ and so on until $a_{s-n}=a^n>d$ which is ofc less than $ad$ by Claim 1, therefore such exponent is achievable. By Claim 2 the problem is solved thus we are done .

Note that if $\gcd(a,d) \neq 1$, then the answer is $0$, since each term will be $1$ mod the gcd and the division never occurs. Claim: all elements in the sequence are smaller than $ad$ Proof: Let $x$ be an element in the sequence from $0$ to $d-1$. Take $x,x+d,x+2d,...,x+(a-1)d$ Note that out of all these terms, one of them divides $a$. Note that because there are $a$ terms, for none of the terms to divide $a$, two of them have to have the same remainder mod $a$. As a result, $x+bd \equiv x+cd \pmod a$ $bd \equiv cd \pmod a$ $b \equiv c \pmod a$. Because $b$ and $c$ are between $0$ and $a-1$, this is impossible and creates a contradiction. Note that all of these terms are less than $d+(a-1)d=ad$, so the entire sequence is less than $ad$. Claim: the entire sequence loops Proof: Due to the upper bound, two elements have to be the same, so the sequence has to have a loop. Let $y$ be the common element. Then, go backwards from the two elements. If $y<d$, then the only possible previous value is $ya$. If $y \ge d$, then the only possible value is $y-a$, since $ya$ is too big. So the previous elements of both of the common elements are also the same. This can be repeated until the $1$ at the start is reached, so the $1$ is part of a loop The number before the $1$ has to be $a$, and the number before $a$ has to be $a^2$, and this repeats until the value is greater than or equal to $d$. This happens when the value is equal to $a^{\lceil \log_a(d) \rceil}$, so the maximum possible power of $a$ is $\boxed{\lceil \log_a(d) \rceil}$. Note that a value bigger than that is impossible, since it would be above the upper bound of $ad$.