2022 AMC 10B Problem 25

$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}$.

The sequence is the binary expansion of $\frac17$ in the $2$-adic sense: each $S_n$ is the unique residue inverting $7$ modulo $2^n$, and these residues are consistent because they are truncations of one infinite bit string. The $3$-periodicity comes from $2^3 \equiv 1 \pmod 7$, exactly as $\frac17 = 0.\overline{142857}$ has period $6$ because $10^6 \equiv 1 \pmod 7$. Computing small cases reveals the pattern; a single identity ($7 \cdot \frac{2^{3m}-1}{7} = 2^{3m} - 1$) proves it.

The bits are the $2$-adic expansion of $\tfrac17$. Since $7 = 8 - 1$, we have $-\tfrac17 = 1 + 8 + 8^2 + \cdots$, whose binary digits are $\ldots 001\,001\,001$. Negating in binary (complement every bit, then add $1$) gives $\tfrac17 = \ldots 110\,110\,111_2$, the same pattern: $x_0 = 1$, then blocks $0, 1, 1$ upward. Truncating this string to $n$ bits gives exactly the residue $S_n$ with $7S_n \equiv 1 \pmod{2^n}$.

• Assuming the bits repeat 111 or 011 from the first few (x₀ = x₁ = x₂ = 1) without computing far enough to see the period-3 pattern 0,1,1.
• Misaligning the period: $x_k = 0$ for positive multiples of $3$, so $x_{2019}$ and $x_{2022}$ vanish; shifting by one gives $7$ or $12$ instead of $6$.