Skip to main content

2022 AMC 12B Problem 23

Problem 23 of 25HarderNumber Theory

Let x0,x_0, x1,x_1, x2,x_2, \ldots be a sequence of numbers, where each xkx_k is either 00 or 1.1. For each positive integer n,n, define Sn=k=0n1xk2k.S_n = \sum_{k=0}^{n-1} x_k 2^k. Suppose 7Sn1(mod2n)7 S_n \equiv 1 \pmod{2^n} for all n1.n \ge 1. What is the value of the sum x2019+2x2020+4x2021+8x2022?x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}?

Answer choices

Show solution

Solution

Since SnS_n is the integer formed by the low nn bits, the condition 7Sn17S_n \equiv 1 means Sn71(mod2n)S_n \equiv 7^{-1} \pmod{2^n} for every n.n. Thus the digits xkx_k are the base-22 digits of 17\tfrac17 as a 22-adic number. Long division in base 22 gives digits x0=x1=x2=1,x_0 = x_1 = x_2 = 1, and thereafter the block repeats with period 3:3: for k1,k \ge 1, xk=0x_k = 0 exactly when kk is divisible by 3,3, and xk=1x_k = 1 otherwise. Since 20192019 and 20222022 are both divisible by 3,3, while 202012020 \equiv 1 and 20212(mod3),2021 \equiv 2 \pmod 3, we get x2019=0,x_{2019} = 0, x2020=1,x_{2020} = 1, x2021=1,x_{2021} = 1, x2022=0.x_{2022} = 0. The sum is 0+2+4+0=6.0 + 2 + 4 + 0 = 6. Thus, the correct answer is A.

More practice

Concepts: modular arithmetic · number base · pattern recognition

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.