For any integer , define as the greatest integer less than or equal to . For any positive integer , let For how many values of , is odd?
Solution
55 Notice that, for fixed counts the number of integers which are divisible by ; hence, counts the number of pairs with divisible by . For any fixed , the number of such pairs is (the number of divisors of ), so the total number of pairs equals . But is odd precisely when is a square, so is odd precisely when there are an odd number of squares in . This happens for . Adding these up gives 55 values of .
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.