2022 AMC 10B Problem 25

Problem 25 of 25HarderNumber Theory

Let

x_0,

x_1,

x_2,

\dotsc

be a sequence of numbers, where each

x_k

is either

0

or

1.

For each positive integer

n,

define

S_n = \sum_{k=0}^{n-1} x_k 2^k

Suppose

7S_n \equiv 1 \pmod{2^n}

for all

n \geq 1.

What is the value of the sum

x_{2019} + 2x_{2020} +

4x_{2021} + 8x_{2022}?

Show solution

Solution

The desired sum is

\frac{S_{2023}-S_{2019}}{2^{2019}}.

Also,

0\le S_n<2^n.

Therefore, for a unique

m_n\in\{0,1,\ldots,6\},

7S_n=m_n2^n+1.

Reducing modulo

7

gives

m_n2^n\equiv-1\pmod7.

Since

2^3\equiv1\pmod7

and

2019\equiv0\pmod3,

we get

m_{2019}=6.

Since

2023\equiv1\pmod3,

we have

2m_{2023}\equiv-1\pmod7,

so

m_{2023}=3.

Hence

\begin{gathered}S_{2019}=\frac{6\cdot2^{2019}+1}{7},\\ S_{2023}=\frac{3\cdot2^{2023}+1}{7}.\end{gathered}

Finally,

\frac{S_{2023}-S_{2019}}{2^{2019}} =\frac{3\cdot2^4-6}{7}=6.

Thus, the correct answer is A .

More practice

Concepts: modular arithmetic · number base · power of 2

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.