1994 AIME Problem 4

Question

Find the positive integer

n

for which

\begin{aligned}&\lfloor\log_2 1\rfloor+\lfloor\log_2 2\rfloor+\lfloor\log_2 3\rfloor\\&\quad+\cdots+\lfloor\log_2 n\rfloor=1994.\end{aligned}

(For real

x,

\lfloor x\rfloor

is the greatest integer not exceeding

x.

)

Answer

Group integers having the same value of

\lfloor\log_2 k\rfloor

Compute the sum through

255

, after which every new term initially contributes

8

For

2^j\leq k<2^{j+1},

the summand is

j.

Thus the sum through

255=2^8-1

is

\sum_{j=0}^7j2^j=(8-2)2^8+2=1538.

The remaining

1994-1538=456

is

57\cdot8,

so we include

57

more integers beginning with

256.

Hence

n=255+57=312.

Problem 4 in other years