Question

There exists a unique strictly increasing sequence of nonnegative integers $a_1 \lt a_2 \lt \cdots \lt a_k$ such that $\frac{2^{289} + 1}{2^{17} + 1} = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k}.$ What is $k?$

$117$

$136$

$137$

$273$

$306$

Solution:

Let $x = 2^{17}.$ Then $\dfrac{2^{289} + 1}{2^{17} + 1} = \dfrac{x^{17} + 1}{x + 1} = x^{16} - x^{15} + \cdots - x + 1,$ an alternating sum of the $17$ powers $x^0, x^1, \ldots, x^{16}.$

Pair each subtracted power with the added power just above it: $x^{m+1} - x^m = 2^{17m}(2^{17} - 1) = 2^{17m} + 2^{17m+1} + \cdots + 2^{17m+16},$ a block of $17$ consecutive powers of $2.$

There are $8$ such pairs, together with the leftover $+2^0.$ The blocks occupy disjoint ranges, so the total number of powers is $8 \cdot 17 + 1 = 137.$

Thus, C is the correct answer.

2020 AMC 12A Problem 19

Solution:

Problem 19 in Other Years