2022 AMC 10 B Problem 25

One Page to Learn. One Point to Earn.

In This Page:

To help you master 2022 AMC 10 B Problem 25, this page includes:

• The original AMC problem to try, plus the correct answer

• Clear, step-by-step solutions using different methods

• Key ideas, useful formulas, and takeaways you can apply to similar problems

• Related problems from past AMC exams, plus new practice problems that build the same skills

Want more practice? Scroll down to download Think Academy’s AMC 10 practice packs and keep building your AMC 10 B skills.

2022 AMC10 B Problem 25

Solution

Solution 1

Iterative Sequence and State Machine Method

We can compute the terms $x_k$ one by one. By defining an integer ‘carry’ for each step, we can show that the process acts like a state machine. Once the carry repeats, the sequence of bits must enter a repeating cycle.

State Machine Recurrence: To find the digits of a number under a multiplicative condition, track the ‘carry’ at each step. Because the next digit and next carry are uniquely determined by the current carry, any repeating carry guarantees a permanent cycle in the digits.

Step 1: Define a state sequence for the remainder

Since $S_n$ is an integer, the condition means $7S_n$ leaves a remainder of $1$ when divided by $2^n$. We can define an integer sequence $M_n$ representing the ‘carry’ at each step.

$$7S_n=1+M_n{2}^n$$

Step 2: Establish the recurrence relation for the bits and states

We know the next partial sum $S_{n+1}$ is built by adding the next bit. Substituting this into the modulo definition gives a direct algebraic relationship between the old carry $M_n$, the new carry $M_{n+1}$, and the next bit $x_n$.

$$S_{n+1}=S_n+x_n{2}^n$$

$$7(S_n+x_n{2}^n)=1+M_{n+1}{2}^{n+1}$$

$$1+M_n{2}^n+7x_n{2}^n=1+M_{n+1}{2}^{n+1}$$

$$(M_n+7x_n)2^n=M_{n+1}{2}^{n+1}$$

$$M_n+7x_n=2M_{n+1}$$

Step 3: Determine the rules for finding the bit and next state

Since $2M_{n+1}$ is an even number, the sum $M_n+7x_n$ must be even. Because $7$ is odd, $7x_n$ has the same parity as $x_n$. Thus, $x_n$ must be chosen from $\{0,1\}$ so that it matches the parity of $M_n$. After finding $x_n$, we calculate the next state $M_{n+1}$.

$$x_n\equiv M_n(\mathrm{mod}2)$$

$$M_{n+1}=\frac{M_n+7x_n}{2}$$

Step 4: Iterate to find the repeating pattern

First, find the initial state $M_0$ using the empty sum $S_0=0$. Then apply the parity and carry rules sequentially. For negative states, we still choose $x_n\in \{0,1\}$ based on whether the state is even or odd.

$$n=0:7(0)=1+M_0{2}^0⟹M_0=-1$$

$$n=0:M_0=-1⟹x_0=1⟹M_1=\frac{-1+7(1)}{2}=3$$

$$n=1:M_1=3⟹x_1=1⟹M_2=\frac{3+7(1)}{2}=5$$

$$n=2:M_2=5⟹x_2=1⟹M_3=\frac{5+7(1)}{2}=6$$

$$n=3:M_3=6⟹x_3=0⟹M_4=\frac{6+7(0)}{2}=3$$

Step 5: Evaluate the requested sum

Notice that $M_4=M_1=3$. This means the states and bits repeat in a cycle of length 3 starting from $n=1$. Looking at the cycle ($x_1=1,x_2=1,x_3=0$), the bit $x_k$ is $0$ when $k$ is a multiple of 3, and $1$ otherwise. We can now evaluate the four required terms.

$$2019=3\times 673⟹x_{2019}=0$$

$$x_{2020}=1$$

$$x_{2021}=1$$

$$x_{2022}=0$$

$$x_{2019}+2x_{2020}+4x_{2021}+8x_{2022}=0+2(1)+4(1)+8(0)=6$$

Correct answer: A. $6$
The value of the sum is 6, which corresponds to choice A. We can verify this by checking the actual values of $S_n$. For example, $S_4=1+2+4+0=7$, and $7(7)=49=1+3(16)$, which correctly leaves a remainder of 1 modulo 16.

Solution 2

Algebraic Structure and Two’s Complement Method

Instead of finding digits sequentially, we can satisfy $7S_n\equiv 1(\mathrm{mod}{2}^n)$ by algebraically expressing $1/7$ modulo $2^n$. The relation $2^3-1=7$ allows us to use the geometric series formula to find the binary expansion of $-1/7$, which we can negate using binary complement arithmetic.

Two’s Complement: In modular arithmetic, $-X(\mathrm{mod}{2}^N)$ can be evaluated by subtracting $X$ from $2^N-1$ (which flips all the binary bits of $X$) and then adding 1.

Step 1: Connect the factor 7 to powers of 2

The problem involves multiplication by 7 modulo $2^n$. Notice that $7=2^3-1$. By substituting this into the algebraic factorization of $2^{3m}-1$, we can relate 7 to a geometric series of powers of 2.

$$2^{3m}-1=(2^3-1)(1+2^3+2^6+\cdots +2^{3m-3})$$

$$2^{3m}-1=7\sum _{j=0}^{m-1}{2}^{3j}$$

Step 2: Solve algebraically for the sequence sum

Consider the arithmetic modulo $2^{3m}$. Since $2^{3m}-1\equiv -1(\mathrm{mod}{2}^{3m})$, we can substitute this into our series identity. Because 7 is odd, it has a unique inverse modulo $2^{3m}$, allowing us to directly solve for $S_{3m}$.

$$7\sum _{j=0}^{m-1}{2}^{3j}\equiv -1(\mathrm{mod}{2}^{3m})$$

$$7\left(-\sum _{j=0}^{m-1}{2}^{3j}\right)\equiv 1(\mathrm{mod}{2}^{3m})$$

$$S_{3m}\equiv -\sum _{j=0}^{m-1}{2}^{3j}(\mathrm{mod}{2}^{3m})$$

Step 3: Apply two’s complement to resolve the negative sign

We need $-X(\mathrm{mod}{2}^{3m})$ as a sum of positive powers of 2. In binary arithmetic, we can compute this using the identity $(2^N-1)-X+1$. The term $2^{3m}-1$ is a sum of all powers of 2 up to $3m-1$ (a string of 1s in binary). Subtracting our series removes exactly the powers of 2 that are multiples of 3, essentially flipping the bits.

$$X=\sum _{j=0}^{m-1}{2}^{3j}$$

$$-X\equiv (2^{3m}-1)-X+1(\mathrm{mod}{2}^{3m})$$

$$(2^{3m}-1)-X=\sum _{k=0}^{3m-1}{2}^k-\sum _{j=0}^{m-1}{2}^{3j}$$

$$(2^{3m}-1)-X=\sum _{k\not\equiv 0(\mathrm{mod}3)}^{3m-1}{2}^k$$

Step 4: Add 1 to complete the binary representation

The final step to find $-X$ is to add 1. Because $k=0$ is a multiple of 3, the sum from the previous step does not include $2^0=1$. Adding 1 simply includes $2^0$ as a distinct term without triggering any carry chains. This gives the complete binary expansion.

$$S_{3m}=1+\sum _{k\not\equiv 0(\mathrm{mod}3)}^{3m-1}{2}^k$$

$$S_{3m}=2^0+\sum _{k\not\equiv 0(\mathrm{mod}3)}^{3m-1}{2}^k$$

Step 5: Extract the bits and evaluate the sum

This algebraic formula perfectly determines which bits $x_k$ are $1$. Because it applies for any large integer $m$, it governs the entire sequence. We use the resulting rule to find the requested indices and calculate the final answer.

$$x_0=1$$

$$x_k=0\text{if}k\equiv 0(\mathrm{mod}3)(k\ge 1)$$

$$x_k=1\text{if}k\not\equiv 0(\mathrm{mod}3)(k\ge 1)$$

$$x_{2019}+2x_{2020}+4x_{2021}+8x_{2022}=0+2(1)+4(1)+8(0)=6$$

Correct answer: A. $6$
The value of the sum is 6, matching choice A. As a final check on the algebraic structure, $S_6=1+2+4+16+32=55$. Multiplying by 7 gives $55\times 7=385$. Since $385=6\times 64+1$, $7S_6\equiv 1(\mathrm{mod}64)$, confirming that the formula perfectly satisfies the original condition.

Similar Problems in Real Exams

The following five AMC 10 B problems are closely related to AMC 10 B 2022 Question 25. These real AMC 10 B problems test the same key concept—Modular Arithmetic. Click any problem to learn and practice, then continue to the adapted practice section later in this article for more problems to try.

2025 AMC 10 B Problem 4

2021 AMC 10 B Problem 13

2025 AMC 10 B Problem 2

2024 AMC 10 B Problem 4

2024 AMC 10 B Problem 7

Adapted Problems to Practice

What Formulas Do You Need for This Problem?

• Geometric Series Factorization:

$x$ is any real number and $N$ is a positive integer. Setting $x=2^3$ creates a natural bridge between $2^3-1=7$ and a binary series.

• Two's Complement in Modular Arithmetic:

$X$ is a non-negative integer less than $2^N$. It converts a negative binary sequence into a standard sum of distinct positive powers of 2. Since $2^N-1={\sum }_{k=0}^{N-1}{2}^k$, subtracting $X$ simply removes the powers of 2 present in $X$ (flipping its bits).

Key Takeaway: Remember This Strategy for Next Time

Unlock More Targeted AMC 10 Practice Resource

Build Stronger Skills. Practice with Purpose. Prepare with Confidence.

Get a complete set of module-focused AMC 10 practice workbooks designed to help students strengthen core concepts, improve problem-solving strategies, and feel more confident on test day.

With 250+ practice problems organized across six essential AMC 10 modules, students can focus on one skill area at a time and learn from clear, step-by-step solutions.

Download the Free AMC 10 Practice Resource Pack

Inside, You’ll Find:

• 6 module-focused practice workbooks: Algebra, Geometry, Number Theory, Combinatorics, and Probability & Statistics.
• 250+ AMC 10-style practice problems covering essential concepts and common competition question types.
• Complete answer keys and step-by-step solutions to help students understand the reasoning behind each answer.
• Organized, print-ready materials for independent study, guided practice, or extra preparation at home.

Get Instant Access: Fill out the form below to receive our exclusive resource pack.

*Please enter a valid email address to access the materials and receive future prep updates.

About Think Academy

Think Academy US Online, part of TAL Education Group (NYSE: TAL), provides structured math and ELA programs that help students build strong academic foundations and grow with confidence. With expert teachers, proven methods, and innovative AI tools, we nurture learning ability, curiosity, and healthy study habits that support long-term growth and a lifelong love of learning.

Check our programs:

• Think Kids: Ages 3-5
• Math
  • Lower Elementary Math — Grades 1–2
  • Upper Elementary Math — Grades 3–5
  • Middle School Math — Grade 6–8
  • High School Math — Grade 9-12
• ELA
  • Elementary ELA — Grades 2–5

Want more insights on Math & ELA learning and parenting? Fill out the form on this page and subscribe to our newsletter for weekly tips and the latest resources. Join 100,000+ families in our Parent Community!