16
$\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$
3

3 Answers 3

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$
5
$\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$
1
  • $\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
    Commented Sep 17, 2013 at 17:23
4
$\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 \ge q_2 \ge \dots \ge 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .