# 1986 AHSME Problems/Problem 25

## Problem

If $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$, then $\sum_{N=1}^{1024} \lfloor \log_{2}N\rfloor =$ $\textbf{(A)}\ 8192\qquad \textbf{(B)}\ 8204\qquad \textbf{(C)}\ 9218\qquad \textbf{(D)}\ \lfloor\log_{2}(1024!)\rfloor\qquad \textbf{(E)}\ \text{none of these}$

## Solution

Because $1 \le N \le 1024$, we have $0 \le \lfloor \log_{2}N\rfloor \le 10$. We count how many times $\lfloor \log_{2}N\rfloor$ attains a certain value.

For all $k$ except for $k=10$, we have that $\lfloor \log_{2}N\rfloor = k$ is satisfied by all $2^k \le N<2^{k+1}$, for a total of $2^k$ values of $N$. If $k=10$, $N$ can only have one value ( $N=1024$). Thus, the desired sum looks like $$\sum_{N=1}^{1024} \lfloor \log_{2}N\rfloor =1(0)+2(1)+4(2)+\dots+2^k(k)+\dots+2^{9}(9)+10$$

Let $S$ be the desired sum without the $10$. $$S=2(1)+4(2)+\dots+2^{9}(9)$$ Multiplying by $2$ gives $$2S=4(1)+8(2)+\dots+2^{10}(9)$$ Subtracting the two equations gives $$S=2^{10}(9)-(2+4+8+\dots+2^9)$$ Summing the geometric sequence in parentheses and simplifying, we get $$S=2^{10}(9)-2^{10}+2=2^{10}(8)+2=8194$$ Finally, adding back the $10$ gives the desired answer $\fbox{(B) 8204}$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 