Let be the number of triples of positive integers satisfying . Compute the remainder when is divided by 1000.
Solution
Let . If we let , then the number of ordered triples that satisfy the second and third conditions is the number of nonnegative solutions to and , where at least one of is zero and at least one of is zero (otherwise, ). By complementary counting, the number is Let be the number of unordered triples with distinct, and the number of unordered triples with two numbers equal. Since it is impossible for , we have . We now count . Without loss of generality, assume . For the factors of 2, we have two choices: either assign to or assign to both and . We have a similar two choices for the factors of 3. Therefore . 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.