For positive integers , let be the largest factor of other than itself. Determine the number of ordered pairs of composite positive integers for which .
Solution
Let be an integer, and let be the smallest prime factor of . Then, if , we note that we must have for some prime . (Otherwise, if , then . If is composite, then for some factor of .)
So we have:
- value for
- values for
Hence, we note that, since and are composite, we cannot have or , so the possible pairs are and vice-versa.
We add the number of choices for each pair, and double since and are interchangeable, to get possible ordered pairs .
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.