How many different numbers can be formed by the product of two or more of the numbers 3, 4, 4, 5, 5, 6, 7, 7, 7?
Answers
Note that picking a certain subset from {3,4,4,5,5,6,7,7,7} will uniquely determine the prime factorization of such a number. Even if we pick 6 (which is not coprime to 3 or 4), we will still have a number that is uniquely determined, because the exponent of 2 will be odd regardless of what other numbers are picked.
Hence, we have two ways to pick the number of 3's (0 3's or 1 3), three ways to pick the number of 4's, three ways for 5's, two ways for 6's, and four ways for 7's. Multiplying, this becomes 2*3*3*2*4 = 144. However, we need to subtract the size of the set obtained when we pick zero or one numbers. This is easy to count; only {1, 3, 4, 5, 6, 7} can only be picked by choosing zero or one elements. Thus the total number of numbers that satisfy is 144 - 6 = 138.