2005 AIME I Problems/Problem 12
Problem
For positive integers let denote the number of positive integer divisors of including 1 and For example, and Define by Let denote the number of positive integers with odd, and let denote the number of positive integers with even. Find
Solution
It is well-known that is odd if and only if is a perfect square. (Otherwise, we can group divisors into pairs whose product is .) Thus, is odd if and only if there are an odd number of perfect squares less than . So and are odd, while are even, and are odd, and so on.
So, for a given , if we choose the positive integer such that we see that has the same parity as .
It follows that the numbers between and , between and , and so on, all the way up to the numbers between and have odd, and that these are the only such numbers less than (because ).
Thus .
Similarly, , where the accounts for those numbers between and .
Then .
We must now apply the formula . From this formula, it follows that and so that . Thus,
.