Online Course Discussion Forum

Quick Question on a Simple Problem

 
 
Picture of Tina Jin
Quick Question on a Simple Problem
by Tina Jin - Monday, January 1, 2024, 5:55 PM
 

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

 
Picture of John Lensmire
Re: Quick Question on a Simple Problem
by John Lensmire - Thursday, January 4, 2024, 5:43 PM
 

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!

Picture of Tina Jin
Re: Quick Question on a Simple Problem
by Tina Jin - Thursday, January 4, 2024, 9:16 PM
 

That's interesting how810810000 is actually the smallest. Thank you for your detailed response!