MathDB

Add d or Divide by a

Source: ISL 2022 N3

July 9, 2023

number theoryISL 2022IMO ShortlistSequence

Problem Statement

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

.

Back to Problems View on AoPS