Online Course Discussion Forum
Quick Question on a Simple Problem
Hello,
For problems like "find the smallest number that has n factors", it is easy to see which numbers that have n factors are greater than the other if n is small. for example if n has 6 factors, clearly 2^5>2^2*3
But for much larger "n"s, it is impractical to multiply everything out, so it is harder to see which one is greater than the other. For example, if n=1000, then is ?
Thanks,
Tina Jin
Answering before the others because I was curious about the "quick question".
Short answer: It's actually a complicated question to find the smallest number with exactly n factors for various n :)
To have $1000$ factors, a number must be of the form $p^999$ or $p^499\cdot q$ or $p^249\cdot q\cdot r$ etc.
Easy Observation: For a given form, the smallest number has $p=2$, $q=3$, etc. This helps because that means there's a unique number you need to consider for each form. Hence, in your example, you really should be comparing $2^9 3^4 5^4 7^3$ to $2^9 3^9 5^9$ which is a little easier because it becomes comparing $7^3$ to $3^5 5^5$ after cancelling.
Rough Intuition: Exponents grow fairly fast, so at least to start, typically using more primes gives a smaller number. Looking at $2^9 3^4 5^4 7^3$ as an example, clearly swapping $2^9$ for $2^4 11$ (so we still are multiplying by $10$ in our number of factors formula) gives a smaller number as $2^5 > 11$. That being said, note that even $2^3$ is smaller than $13$ (the 'next' prime) so we probably don't want to break down $2^4$ any further. This is where things get complicated.
Answer for 1000: Just for reference the smallest number with $1000$ factors is $2^4 3^4 5^4 7 11 13 = 810810000$, but this is NOT immediately obvious.
If you're curious check out the sequence "Smallest number with exactly n divisors" by clicking here as evidence that there are NOT very nice patterns!
Social networks