For a positive integer , let, be the number of positive integer divisors of . How many integers are there such that is odd?
Solution
Note that is odd if and only if is a perfect square. Thus, it suffices to find the number of integers in the given range such that for some positive integer . If , then we obtain as our only solution. If , we see that is either in the form or , where and are distinct primes. The first subcase gives solutions, while the second subcase gives 2 solutions. implies that is a perfect square, and it is easy to see that only works. Finally, implies that is greater than 50, so we've exhausted all possible cases. Our final answer is .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.