2020 AMC 10A Problem 21

Since $289 = 17^2$, set $x = 2^{17}$. Then $2^{289} = x^{17}$ and the fraction becomes
$$\frac{x^{17} + 1}{x + 1} = x^{16} - x^{15} + x^{14} - \cdots - x + 1,$$
the standard factorization of a sum of odd powers. The question asks how many $1$s this number has in binary, since the $a_i$ are the positions of the $1$ bits.

The alternating signs must be removed. Group consecutive pairs:
$$(x^{16} - x^{15}) + (x^{14} - x^{13}) + \cdots + (x^2 - x) + 1.$$
Each pair is $x^{2j-1}(x - 1) = 2^{17(2j-1)} \cdot (2^{17} - 1)$. In binary $2^{17} - 1$ is seventeen $1$s, and multiplying by a power of $2$ just shifts, so each pair contributes exactly $17$ ones, occupying bits $17(2j-1)$ through $17 \cdot 2j - 1$. These bit ranges for $j = 1, \dots, 8$ are disjoint and never touch bit $0$, where the lone $+1$ sits.

Counting: $8$ pairs $\times$ $17$ ones $+ 1 = 137$.

The answer is $\boxed{\textbf{(C)}\ 137}$.

A quotient like $\frac{a^n + 1}{a + 1}$ is a polynomial in $a$ with alternating coefficients; to read it in base $a$ (here base $2$ blocks of width $17$) you must convert each negative coefficient into a "borrow," which in binary turns $x^{m+1} - x^m$ into a run of ones. Try the tiny analogue $\frac{2^9 + 1}{2^3 + 1} = 57 = 111001_2$: one pair contributing $3$ ones plus the final $1$, four ones in all, matching the formula $1 \cdot 3 + 1$.

• Counting the 17 alternating terms as 17 powers of two, or getting 8 * 17 = 136 and forgetting the final +1.
• Miscounting the number of pairs (there are $8$ pairs among the $16$ terms of degree $1$ to $16$) or using $16$ ones per block.