15
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For multicharacter exponents, put them in braces. So 2^{11} to get $2^{11}$ Also, \min gets it set as a function. $\endgroup$ – Ross Millikan Sep 17 '13 at 15:51
  • $\begingroup$ oeis.org/A005179 $\endgroup$ – barrycarter Sep 7 '17 at 19:17
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @ Michael That's what I tried at first,this algorithm becomes laborious if we are dealing with such numbers whose number of divisors has many prime factors,so I want a generalized method in order to avoid comparing numbers>>> $\endgroup$ – Tom Lynd Sep 17 '13 at 17:23
1
$\begingroup$

A005179 lists some resources on the problem. In particular:

Grost, M. (1968). The Smallest Number with a Given Number of Divisors. The American Mathematical Monthly, 75(7), 725-729. doi:10.2307/2315183

From the introduction:

Given $h = q_1 q_2 \dots q_n$, with primes $q_1 \le q_2 \le \dots \le q_n$, let $A(h)$ be the smallest number with $h$ divisors.

In many cases, $$A(h) = 2^{q_1-1} 3^{q_2-1} \dots p_n^{q_n-1}$$

The primary objective of the paper is to determine the exceptions.

We call these numbers ordinary, from R. Brown, The minimal number with a given number of divisors, Journal of Number Theory 116 (2006) 150-158. In this paper Brown shows almost all $A(h)$ are ordinary, in particular "We show here that all square-free numbers are ordinary and that the set of ordinary numbers has natural density one."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.