Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
2  
$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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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