2022 AMC 10B Problem 25

$S_n$ is the number whose binary digits, from the right, are $x_0, x_1, \ldots, x_{n-1}$. The condition $7S_n \equiv 1 \pmod{2^n}$ means: $7S_n$ leaves remainder $1$ when divided by $2^n$. The target $x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}$ just needs the four bits $x_{2019}$ to $x_{2022}$.

1. Only one choice at each stage. $S_n$ is between $0$ and $2^n - 1$. If two such numbers $A$ and $B$ both worked, $7(A - B)$ would be a multiple of $2^n$. Since $7$ is odd, $A - B$ itself would be a multiple of $2^n$, so $A = B$. Also, the last $n$ bits of $S_{n+1}$ form a number that passes the test for $2^n$ (dropping the top bit subtracts a multiple of $2^n$, which does not change the remainder), so they form $S_n$. So there is one fixed string of bits, and each $S_n$ is its last $n$ bits.
2. Small cases. Find each $S_n$ by adding the next bit (either $0$ or the next power of $2$) and testing.

Reading from the right: $x_0 = 1$, then $x_1, x_2, x_3 = 1, 1, 0$ and $x_4, x_5, x_6 = 1, 1, 0$. So $x_k = 0$ exactly when $k$ is a positive multiple of $3$.
3. Why the pattern continues. In binary $7 = 111$. Let $T$ be the binary number $001\,001 \ldots 001$ with $m$ blocks. Multiplying by $111$ turns each $001$ into $111$, so $7T = 111\ldots111$ ($3m$ ones) $= 2^{3m} - 1$.
4. Build the answer from $T$. Let $N = 2^{3m} - T$. Then
$$7N = 7 \cdot 2^{3m} - (2^{3m} - 1) = 6 \cdot 2^{3m} + 1,$$
which leaves remainder $1$ when divided by $2^{3m}$. So $N = S_{3m}$.
5. $N$ in binary. $N = (2^{3m} - 1 - T) + 1$. Subtracting $T$ from $111\ldots111$ just flips each bit of $T$, giving $110\,110 \ldots 110$. Adding $1$ gives $110\,110 \ldots 111$. This is exactly the pattern from step 2, for as many blocks as we like.
6. Read off the bits. $2019 = 3 \times 673$ and $2022 = 3 \times 674$ are multiples of $3$, so $x_{2019} = x_{2022} = 0$. The positions $2020$ and $2021$ are not, so $x_{2020} = x_{2021} = 1$.
7. The sum. $0 + 2 \times 1 + 4 \times 1 + 8 \times 0 = 6$.

The answer is $\boxed{\textbf{(A)}\ 6}$.

The bits repeat because $2^3 = 8$ is one more than $7$, just as the decimal digits of $\frac17$ repeat because $10^6 - 1$ is a multiple of $7$. Computing a handful of small cases shows the pattern, and the fact that $7 \times 001001\ldots001 = 111111\ldots111$ in binary proves it. When a problem asks about a far-away term, look for a repeating cycle first.

$S_n$ is the $n$-bit binary number $x_{n-1} \dots x_1 x_0$, so the condition says $S_n$ is the unique inverse of $7$ modulo $2^n$; each $S_n$ is determined, and $S_{n+1}$ adds one bit on top. The desired sum is the $4$-bit block $x_{2022}x_{2021}x_{2020}x_{2019}$.

Small cases (each checked directly, e.g. $7 \cdot 23 = 161 = 5 \cdot 32 + 1$): $S_1 = 1$, $S_2 = 3$, $S_3 = 7$, $S_4 = 7$, $S_5 = 23$, $S_6 = 55$, $S_7 = 55$. The bits $x_0, x_1, \dots$ are $1, 1, 1, 0, 1, 1, 0, \dots$: after $x_0 = 1$ the block $1, 1, 0$ seems to repeat.

Proof of the pattern: since $2^3 \equiv 1 \pmod 7$, the number $T_m = \frac{2^{3m} - 1}{7}$ is an integer, with binary form $001\,001 \dots 001$ ($m$ blocks). Let $N = 2^{3m} - T_m$. Then
$$7N = 7 \cdot 2^{3m} - (2^{3m} - 1) = 6 \cdot 2^{3m} + 1 \equiv 1 \pmod{2^{3m}},$$
and $0 < N < 2^{3m}$, so $S_{3m} = N$. In binary, $2^{3m} - T_m = (2^{3m} - 1 - T_m) + 1$ is the bitwise complement of $T_m$ plus one: $110\,110 \dots 110 + 1 = 110\,110 \dots 111$. Reading from the bottom, $x_0 = 1$ and for $k \ge 1$, $x_k = 0$ exactly when $3 \mid k$.

Take $m = 675$ so $3m = 2025 > 2022$. Then $x_{2019} = 0$ ($2019 = 3 \cdot 673$), $x_{2020} = 1$, $x_{2021} = 1$, $x_{2022} = 0$ ($2022 = 3 \cdot 674$).

The sum is $0 + 2 + 4 + 0 = 6$.

The answer is $\boxed{\textbf{(A)}\ 6}$.