2021 JMC 10 Problems/Problem 15
Problem
Let be a sequence such that
and
for positive integers
How many terms of this sequence are divisible by
Solution
Note that has exactly
ones and the rest are zeroes. By rules of divisibility by 9, the sum of the digits must be a multiple of 9, so we must have
, which have
divisible by 9.
For divisibility of , we claim that
if and only if
is odd. Notice that
,
,
are all divisible by
by the sum of odd powers factorization of
and
. Because
for odd
are just linear combinations of these, they are multiples of
. Because
more than a multiple of a multiple of
is not a multiple of
, even
fail on the basis of odd
's success. Combining, we must have
, and the answer is the number of
that are congruent to
. Thus, the answer is
.