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.

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

For the at least case, you should check out OEIS sequence A002182 which lists the numbers which set records for number of factors. Many references are given. For exactly equal, see A005179 which has the smallest number with a given number of divisors.

  • $\begingroup$ Interesting, thank you. Unfortunately, the references aren't really of much use to me because I cannot seem to access them in their entirety, and (perhaps primarily) because I find it difficult to follow professional mathematics papers, being inexperienced in the field. $\endgroup$ – Aravind May 14 '12 at 2:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Ross Millikan May 14 '12 at 13:05
  • $\begingroup$ Aravind, you can either play around with it with the methods you know, or you can put in the effort to learn the methods that give the best results. $\endgroup$ – Gerry Myerson May 15 '12 at 7:44
  • $\begingroup$ @Ross Millikan: Nice. Gerry Myerson: Indeed. I completely agree with both of you, and I take it in the right spirit. It's only that I have tried playing around and was getting nowhere; rest assured, though, I haven't explored this nearly as much as it seems I ought to. $\endgroup$ – Aravind May 15 '12 at 8:39

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.