2022 AMC 12B Problem 23

Question

Let

x_0,

x_1,

x_2,

\ldots

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

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

for all

n \ge 1.

What is the value of the sum

x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}?

6

7

12

14

15

Answer: A

Concepts:modular arithmetic number base pattern recognition

Difficulty rating: 2270

Small hint:

S_n

is the number formed by the low

n

bits; the condition says

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

Big hint:

So the bits

x_k

are the binary (2-adic) digits of

\tfrac17;

find their repeating pattern

Solution:

Since

S_n

is the integer formed by the low

n

bits, the condition

7S_n \equiv 1

means

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

for every

n.

Thus the digits

x_k

are the base-

2

digits of

\tfrac17

as a

2

-adic number.

Long division in base

2

gives digits

x_0 = x_1 = x_2 = 1,

and thereafter the block repeats with period

3:

for

k \ge 1,

x_k = 0

exactly when

k

is divisible by

3,

and

x_k = 1

otherwise.

Since

2019

and

2022

are both divisible by

3,

while

2020 \equiv 1

and

2021 \equiv 2 \pmod 3,

we get

x_{2019} = 0,

x_{2020} = 1,

x_{2021} = 1,

x_{2022} = 0.

The sum is

0 + 2 + 4 + 0 = 6.

Thus, the correct answer is A.