# Smallest number with a given number of factors

From my rather rudimentary explorations of this fascinating problem, I believe it to be a layered and rewarding subject for investigation.

My question, essentially, is: How do you find the smallest number with a given number of factors? Indeed, as quickly becomes apparent, a distinction is called for between exactly a given number of factors and at least a given number of factors; as such, approaches considering both will be appreciated.

It's a fairly standard result in number theory that the number of distinct factors (including $1$ and itself) of some number $N$, where
$$N = p_1^{a}\cdot\ p_2^{b}\cdot\ p_3^{c} \cdots$$ ($p_1$, $p_2$, $p_3\ldots$ being distinct primes) is $$(a+1)(b+1)(c+1)\cdots$$

Thus, stated mathematically, the question appears to resolve into finding, or rather, finding a method of finding, this: $$\min\{N = 2^{a}\cdot\ 3^{b}\cdot\ 5^{c} \cdots \space| \space (a+1)(b+1)(c+1)\cdots = n \}$$
or, as the case may be, this: $$\min\{N = 2^{a}\cdot\ 3^{b}\cdot\ 5^{c} \cdots \space| \space (a+1)(b+1)(c+1)\cdots \geq n \}$$ ($n$ being the given number of factors).

My crude, trial-and-error approach so far has been factorising $n$ into $n = n_1\cdot n_2\cdot n_3\cdots \space$ and then assigning $a = n_1 - 1,\space b = n_2 - 1,\space c = n_3 - 1,\space \ldots \space$ to get $N$, my only defence being that I tried to factorise sensibly and perceive some sort of pattern or rule at play. I have been unable to obtain anything beyond some common-sense tricks and techniques, though some of them seemed tantalisingly concrete.

I think it's a beautiful problem, and I'm looking for a way of solving it using a clever, universal algorithm. I'd greatly appreciate a comprehensive solution.

-
Fermat studied this problem around 1640 — you can read his solution in most reference books (e.g., Mahoney). – Kieren MacMillan Sep 14 '14 at 1:33

@Aravind: it is a good way to learn some math. You can also play around with it. Increasing $a$ by 1 increases $N$ by a factor 2 and increases the number of factors by $\frac {a+1}a$ If you take logs, you could say the cost of new factors is $\frac {\log (a+1) - \log a}{\log 2}$. This forms the basis of a greedy algorithm-sequentially add in the next prime that is cheapest in this view. It will get you most of A002182 and it is fun to see what it misses. – Ross Millikan May 14 '12 at 13:05