A. What is the lowest number that has exactly 10 distinct positive factors?

B. Exactly 1,000 distinct positive factors?

C. Exactly 1,000,000 distinct positive factors?

Example: The distinct factors of 72 are 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, and 72. Thus 72 has 12 distinct factors.

For part A, the only choices are (1) the 9th power of a prime -- so that a factor could be formed anywhere from p^0 to p^9, or (2) the produce of a prime and the 4th power of a prime -- so that each factor could be formed as (taking p and q as the primes) p^i * q^j, where i is zero or 1 and j is 0 through 4. These are based on choices of 10 powers of one prime factor or two of one prime factor and 5 of the other (including power zero as one of the possibilities).

For the higher numbers (parts B and C), we need to string together more prime factors or allow higher powers of those prime factors. The first (lowest) 12 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.  I list twelve as 1,000,000 is 2^6 * 5^6.  We can form a number as 37^4 * 31^4 * 29^4 * 23^4 * 19^4 * 17^4 * 13 * 11 * 7 * 5 * 3 * 2. Then, its factors can be made with 5 choices for the power of 37, five for the power of 31, etc. and two choices for the powers of each of 13, 11, 7, 5, 3 or 2.

A question is whether a smaller number would do. Lower primes could be used if higher powers were used. For example, if 2^3 were used we'd have 31^4 * 29^4 * 23^4 * 19^4 * 17^4 * 13^4 * 11 * 7 * 5 * 3 * 2^3. This is smaller than the original, as we've multiplied by 4 * 13^3 but divided by 37^4.  So a smaller number will do. The question now is just what the best combination of powers of primes is best.

The criterion for having 1,000,000 factors is that the product of the exponents (each enhanced by one first) used on the primes must be 1,000,000.  Looked at from the other direction, any factorization of 1,000,000 into powers of primes can be used, with each factor decremented by one and used as a power of a prime.  The problem is that 1,000,000 has a lot of factorizations to be checked. Above, we checked only 2*2*2*2*2*2*5*5*5*5*5*5 and 4*2*2*2*2*5*5*5*5*5*5, giving rise to exponents of (1,1,1,1,1,1,4,4,4,4,4,4) and (3,1,1,1,1,5,5,5,5,5,5) respectively.

Posted by Charlie on 2005-07-08 16:20:59