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.