Question

Let $\begin{aligned} N &= \sum_{k=1}^{1000} k \\ &\quad {}\cdot \left(\lceil \log_{\sqrt{2}} k \rceil - \lfloor \log_{\sqrt{2}} k \rfloor\right). \end{aligned}$ Find the remainder when $N$ is divided by $1000.$ (Here $\lfloor x \rfloor$ denotes the greatest integer that is less than or equal to $x,$ and $\lceil x \rceil$ denotes the least integer that is greater than or equal to $x.$ )

Answer

Answer: 477

Concepts:floor and ceiling functions logarithm power of 2 summation

Difficulty rating: 2410

Solution:

The difference $\lceil x \rceil - \lfloor x \rfloor$ equals $1$ when $x$ is not an integer and $0$ when it is. Now $\log_{\sqrt{2}} k$ is an integer exactly when $k = (\sqrt{2})^j$ for some integer $j,$ and for $k$ to be an integer, $j$ must be even — that is, $k$ must be a power of $2.$ The powers at most $1000$ are $2^0, 2^1, \ldots, 2^9 = 512.$

Therefore $\begin{aligned} N &= \sum_{k=1}^{1000} k - \sum_{j=0}^{9} 2^j \\ &= \frac{1000 \cdot 1001}{2} - 1023 \\ &= 500500 - 1023 = 499477, \end{aligned}$ and the remainder upon division by $1000$ is $477.$

2007 AIME I Problem 7

Answer: 477

Difficulty rating: 2410

Solution:

Problem 7 in Other Years