Question

Let $N = \sum_{k=1}^{1000} k\left(\lceil \log_{\sqrt{2}} k \rceil - \lfloor \log_{\sqrt{2}} k \rfloor\right).$ 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.$ )

答案

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 $N = \sum_{k=1}^{1000} k - \sum_{j=0}^{9} 2^j = \frac{1000 \cdot 1001}{2} - 1023 = 500500 - 1023 = 499477,$ and the remainder upon division by $1000$ is $477.$

2007 AIME I Problem 7

Solution:

Problem 7 in Other Years