# On the number divisors of a number

Let $d(n)$ be the number divisors of a natural number $n$. Now let $m$ be a natural number. Find least natural number $n$ such that $d(n)=m$.

Thank you

-
Often we can find $n$ easily. But sometimes the answer depends on subtle size relationships. There will not be a pleasant formula for general $m$. – André Nicolas Jan 15 '13 at 14:06

Sorry, I edited my answer since I misinterpreted the question. However, here is a start point, but I am still thinking about how to end...

First, let us order the prime numbers as $p_1,p_2,p_2\ldots$ such that $p_i<p_{i+1}$ (so that $p_1=2$, $p_2=3$, $p_3=5$, $p_4=7$, $p_5=11$ and so on).

If $$n = \prod_{i=1}^\ell p_i^{\sigma_i} \quad\text{(with p_{i_j}\neq p_{i_k} for i\neq k and \sigma_i\geq 0 \forall i),}$$ then you have $$d(n) = \prod_{i=1}^{\ell}(\sigma_i+1)$$ In fact $t$ is a divisor of $n$ iff $\displaystyle{t=\prod_{i=1}^\ell p_i^{\tau_i}}$ and $0\leq\tau_i\leq \sigma_i$: it follows that each $\tau_i$ can be chosen in $\sigma_i+1$ different ways.

Therefore, in order to be minimum, such $n$ has to be of the form $$n = \prod_{i=1}^\ell p_i^{\sigma_i}$$ with $0<\sigma_\ell\leq\sigma_{\ell-1}\leq\cdots\leq \sigma_1$. I remains to find a minimum decomposition of $\displaystyle{m=\prod_{i=1}^\ell m_i}$ (with $m_1\geq m_2\geq\cdots\geq m_\ell\geq 2$ not necessarily primes or distinct) so that, choosing $\sigma_i=m_i-1$, $~n$ is the least possible.

-
$6 = 2\cdot 3$ has divisors $1, 2, 3, 6$. That's $m = 4$ not $2$. You're counting prime divisors. – Karolis Juodelė Jan 15 '13 at 13:56
@KarolisJuodelė Ups, yeah I misunderstood the question, I am editing right away... – AndreasT Jan 15 '13 at 13:58

If you want exactly $m$ divisors, the answer is not hard. As others have said, if $n=q_1^{a_1}q_2^{a_2}\ldots q_k^{a_k}$ then $d(n)=(a_1+1)(a_2+1)\ldots(a_k+1)$. So start by factoring $m$. Then just choose the ways to allocate those factors to the exponents of the primes, favoring the small ones. If $m$ is a power of $2$, you can just keep doubling the number of factors either by adding a new prime or increasing the exponent of an existing one from $2^j-1$ to $2^{j+1}-1$, whichever is cheaper. The multipliers would go $2, 3, 4=2^2, 5, 7, 9=3^2, 11, 13, 16=2^4, \ldots$ If $m$ is not a power of $2$ you should start with the largest factors and allocate them. For example let $m=6=2\cdot 3$. First you account for the factor $3$ with $2^2$. Then to double that, you either have to multiply by $3$ or by $8$, so you get $12$.

If you want at least $m$ divisors, the tradeoffs can become subtle, but the general idea is the same.

You might be interested in OEIS A002182 and its references

-