Smallest number with specific number of divisors
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?
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.
Take any number $N=p_1^{m_1}...p_k^{m_k}$, where $p_i$ are its prime divisors, and compute how many divisors it has. Each divisor would be a product of the same primes in varying powers, $D=p_1^{d_1}...p_k^{d_k}$, where $0\leq d_i \leq m_i$. Different divisors have different collections of powers, so the number of divisors will be $(m_1+1)(m_2+1)...(m_k+1)$.
Now let's find the smallest $N$ such that $(m_1+1)(m_2+1)...(m_k+1)=24$. There are only few possibilities to break 24 into a product of decreasing numbers: $3*2*2*2=4*3*2=6*4=6*2*2=8*3=12*2=24$. The corresponding candidates with the smallest primes chosen for the smallest powers would be these ones:
$2^{3-1}*3^{2-1}*5^{2-1}*7^{2-1}=2^2*3*5*7=420$
$2^{4-1}*3^{3-1}*5^{2-1}=2^3*3^2*5=360$
$2^5*3^3=2592$
$2^5*3*5=480$
$2^{11}*3=6144$
$2^{23}=8388608$
Then just pick the smallest one, which happens to be 360.