2020 AMC 10A Problem 21

The right side is just the number written in binary: $k$ is how many $1$s the number has in base $2$. So we need to write the fraction in binary.

A small example first. Try $\frac{2^9 + 1}{2^3 + 1} = \frac{513}{9} = 57$. With $x = 2^3 = 8$, this is $x^2 - x + 1 = 64 - 8 + 1$. Now $64 - 8 = 56$, which is $111000$ in binary: a run of three $1$s. Adding $1$ gives $111001$, with four $1$s in all. The same idea works for the real problem.

1. Simplify. $289 = 17 \times 17$, so $2^{289} = (2^{17})^{17}$. Let $x = 2^{17}$. The fraction is $\frac{x^{17} + 1}{x + 1}$.
2. Divide. Because $17$ is odd, $x + 1$ divides $x^{17} + 1$ evenly, and
$$\frac{x^{17} + 1}{x + 1} = x^{16} - x^{15} + x^{14} - x^{13} + \cdots + x^2 - x + 1.$$
(Check by multiplying by $x + 1$: almost every term cancels, leaving $x^{17} + 1$.)
3. Get rid of the minus signs. Binary allows only plus signs, so group the terms in pairs:
$$(x^{16} - x^{15}) + (x^{14} - x^{13}) + \cdots + (x^2 - x) + 1.$$
There are $8$ pairs.
4. What does one pair look like in binary? Take $x^2 - x = x(x - 1) = 2^{17}(2^{17} - 1)$. The number $2^{17} - 1$ is seventeen $1$s in binary (just as $2^3 - 1 = 7 = 111$). Multiplying by $2^{17}$ shifts it left, adding zeros on the right. So each pair is a run of $17$ ones.
5. Do the runs overlap? The pair $x^2 - x$ fills binary places $17$ through $33$. The pair $x^4 - x^3$ fills places $51$ through $67$, and so on: each pair has its own block, with a gap of $17$ zeros between blocks. The final $+1$ sits at place $0$, which no block touches.
6. Count. $8$ runs of $17$ ones, plus the final $1$: $8 \times 17 + 1 = 137$.

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

A difference like $2^{a} - 2^{b}$ (with $a > b$) is a run of $a - b$ ones in binary. So a sum with alternating signs can be turned into pure binary by pairing each plus term with the minus term right after it. Trying a tiny version of the problem first shows the pattern and catches the easy-to-miss final $+1$.

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