2020 AMC 10A Problem 21

Question

There exists a unique strictly increasing sequence of nonnegative integers

a_1<a_2<\cdots<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

Set

X=2^{17}

and divide

X^{17}+1

by

X+1

Pair positive and negative powers to create blocks of binary ones

Click to load, then click again to play

Let

X=2^{17}

. Then

\begin{gathered} \dfrac{2^{289}+1}{2^{17}+1} = \dfrac{X^{17}+1}{X+1} \\ = X^{16}-X^{15}+X^{14} \\ {}-\cdots-X+1 \end{gathered}

.

Pair consecutive terms:

X^{16}-X^{15}

,

X^{14}-X^{13}

,

\ldots

,

X^2-X

, and then the final

+1

. Each pair is

2^{17m}(2^{17}-1)

, contributing

17

ones in binary. There are

8

such pairs plus the final

1

, so

k=8\cdot17+1=137

. Thus, C is the correct answer.

Problem 21 in other years