2020 AMC 12A Problem 19

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

Write

x = 2^{17};

then the quotient is

\dfrac{x^{17} + 1}{x + 1} = x^{16} - x^{15} + \cdots + 1

Group the alternating terms into pairs

x^{m+1} - x^m = 2^{17m}(2^{17} - 1),

each a block of

17

ones in binary

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.

Problem 19 in other years