AoPSWiki
NEW! Hard Problems DVD
A documentary about the 2006 US IMO team. Features many current and past AoPS members!
Click here for more details and to order
Personal tools

2007 AIME I Problems/Problem 7

From AoPSWiki

Problem

Let N = \sum_{k = 1}^{1000} k ( \lceil \log_{\sqrt{2}} k \rceil  - \lfloor \log_{\sqrt{2}} k \rfloor )

Find the remainder when is divided by 1000. ( is the greatest integer less than or equal to , and is the least integer greater than or equal to .)

Solution

The ceiling of a number minus the floor of a number is either equal to zero (if the number is an integer); otherwise, it is equal to 1. Thus, we need to find when or not is an integer.

The change of base formula shows that \frac{\log k}{\log \sqrt{2}} = \frac{2 \log k}{\log 2}. For the term to cancel out, is a power of . Thus, is equal to the sum of all the numbers from 1 to 1000, excluding all powers of 2 from to .

The formula for the sum of an arithmetic sequence and the sum of a geometric sequence yields that \frac{(1000 + 1)(1000)}{2} - (1 + 2 + 2^2 + \ldots + 2^9) = 500500 - \frac{2^{10}-1}{2-1} = 499477. The solution is .

See also

2007 AIME I (ProblemsResources)
Preceded by
Problem 6
Followed by
Problem 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Looking for a challenging geometry text? Preparing for MATHCOUNTS or the AMC exams? Check out Art of Problem Solving's Introduction to Geometry by Richard Rusczyk.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • FoundationPrivacyContact Us