N3

Part of 2022 IMO Shortlist

Problems(1)

Add d or Divide by a

Source: ISL 2022 N3

a > 1

be a positive integer and

d > 1

be a positive integer coprime to

a

x_1=1

k\geq 1

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

d

, the greatest positive integer

n

for which there exists an index

k

x_k

is divisible by

a^n

number theoryISL 2022IMO ShortlistSequence