1986 AIME Problem 7

Question

The increasing sequence

1,

3,

4,

9,

10,

12,

13,

\ldots

consists of all those positive integers which are powers of

3

or sums of distinct powers of

3.

Find the

100

th term of this sequence.

Answer

These are precisely the numbers whose base-

3

digits are all

0

or

1

Write the index in base

2,

then reinterpret those same digits in base

3

A sum of distinct powers of

3

has only

0

’s and

1

’s in base

3.

As these strings increase, they occur in the same order as binary numerals with the same digit strings. Since

100=1100100_2,

the

100

th positive term is

\begin{aligned} 1100100_3 &=3^6+3^5+3^2\\ &=729+243+9\\ &=981. \end{aligned}

Problem 7 in other years