Is there a general method for finding smallest number of specific number of divisors? I am doing "Higher Algebra by Barnard JM Child" and came across a question that "find the smallest number with 24 divisors", that's how I tried to solve it, alert me if I am wrong:
Since $24$ can not have more than $4$ prime factors, the number can not have more than 4 prime factors.
As a single number it is :$2$^${23}$
as product of two numbers: $2^5*3^3$,$2^{11}*3$,$2^7*3^2$,
since $5+3<7+2<11+1$, so $2^5*3^3$ is the min of these numbers
as product of three numbers :$2^5*3*5$,$2^3*3^2*5$ since $3+2+1<5+1+1$, hence $2^3*3^2*5$ is the lesser of two
as product of 4 numbers $2^2*3*5*7$
$k=\min(2^{23},2^5*3^3,2^3*3^2*5,2^2*3*5*7)$
=$2^3*3^2*5=360$
The above method seems to be fishy and laborious, is there a general approach to find the smallest number with specific number of divisors?
Best Answer
This approach is not fishy at all, but can be laborious. Note that you can't use $5+3 \lt 7+2$ to conclude that $2^5*3^3 \lt 2^7*3^2$, although it is true, you have to take the ratio and use $3 \lt 2^2$. For example, if you were looking for $36$ factors, one comparison would be $2^8*3^3$ versus $2^5*3^5$. Despite the fact that $5+5 \lt 3+8, 2^5*3^5=7776 \gt 6912=2^8*3^3$. You can take logs and compare $5 \log 2 + 3 \log 3$ with $7 \log 2 + 2 \log 3$ to get it right.
I don't know an easier way. Your example shows the failure of a greedy algorithm. Factor the desired number of factors, here as $3*2^3$. Starting from the largest factor, find the cheapest way to get that many. So start with $2^2$, which has $3$ factors. Now you need to double it. You can either multiply by a new prime, clearly $3$, or increase the exponent of $2$ to $5$. Since the first has a factor $3$ and the second $8$, we choose $2^2*3$ Now we want to double again, and our choices are $2^3, 3^2, \text{ or } 5$ and we take $5$, giving $2^2*3*5$ One more doubling comes from $7$, and we come up with $2^2*3*5*7=420$, not the best.