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.
NOTE: I'm assuming the problem means find the lowest positive integer w/ 10 distinct factors
For an arbitrary positive integer X, X factors uniquely as:
- X = p1^n1 * p2^n2 * ... * pk^nk
where p1 .. pk are the k distinct prime factors, and n1 .. nk are the numbers of times each prime appears. Let Y be an arbitrary factor of X. Each pi appears as a factor of Y of some number of times between 0 and ni (inclusive), which gives us ni+1 possible powers for each pi. This means, to find all factors of X, we need only find all possible combinations of allowable powers for each pi. The powers of the pi's are independent, so we have
- #of factors = (n1+1) * (n2+1) * ... * (nk+1).
Let F be the fixed number of factors. F itself factors into primes, each appearing some number of times. Consider ordering the prime factors of F in descending order with duplicates allowed, call them f1 .. fk. For example, if F = 60, the ordering would be {f1=5, f2=3, f3=2, f4=2} [NOTE: this is subtly different from the factoring scheme above in that it counts duplicate factors separately]. I claim that, in cases A, B, and C, the smallest positive integer with F factors is the case where ni = fi - 1 for i = 1 .. k, and p1 .. pk are the first k primes in increasing order.
For example, let F = 10 as in part A. 10 factors into 2*5, so f1=5 and f2=2, and thus n1 = 4 and n2 = 1. 2 and 3 are the first primes, so p1 = 2 and p2 = 3. Altogether we have 2^4 * 3^1 = 48, which factors into {1,2,3,4,6,8,12,16,24,48}.
By this method, cases B and C are:
- B) 2^4 * 3^4 * 5^4 * 7 * 11 * 13 = 810,810,000
- C) 2^4 * 3^4 * 5^4 * 7^4 * 11^4 * 13^4 * 17 * 19 * 23 * 29 * 31 = ~1.8*10^26
It remains to show that indeed the lowest positive integer with F factors is the one generated by our sequence f1 .. fk in our cases. Clearly, having them in decreasing order (technically non-increasing order) with p1 ... pk increasing minimizes the result for that set of fi's, but the fi's need not consist only of prime factors. The only condition on the fi's is that f1 * ... * fk = F.
Consider case C), where the prime factors are 1000000 = 5*5*5*5*5*5*2*2*2*2*2*2 (= 5^6*2^6 for notational convenience). One possible change is to factor into 10*5^5*2^5, which would be an improvement if p1^5 < p12, but p1^5 = 32 > 31 = p12, so this isn't an improivement. Another possible change is 5^6*4*2^3. This is an improvement if p7^2 < p12, but p7^2 = 289 > 31 = p12, so again no improvement. The last possible change is to have 25*5^3*2*6. this is an improvement if p1^20 < p6^3 * p12, but again p1^20 = 1048576 > 68107 = p6^3 * p12. Since any factoring must be achievable by applying the above changes to the all-prime factoring, and since none are improvements, we can say our result is the minimum. Since 10 and 1000 are factors of 1000000, the differences between the primes that were affected by changes in case C are more pronounced than either of the other two cases. this means C was our best chance of the three to have an improvement using non-prime factors, so the other cases are already minimized as well. QED
Kudos to anyone who actually read this far (and sorry for incomplete proof). Anyone want to come up with a general rule for an arbitrary F?
general(ish) sol'n (w/o computer)
