Return to Revisions

The problem asks for the least number $N$ such that the number of divisors of $N$ is at least $n+2$. Since all numbers below $N$ must have fewer divisors, clearly $d(N) > d(m)$ for all $1\le m < N$. Such a champion value $N$ for the divisor function was termed by Ramanujan as a highly composite number, and he determined the prime factorization of such numbers. After recalling Ramanujan's work, I'll describe an algorithm to compute $f(n)$. It executes in time $$ O((\log n)^{C\log \log \log n}), $$ for some constant $C$. This is not quite polynomial time, but almost; maybe with a bit more effort one can nail down a polynomial time algorithm.

Every highly composite $N$ may be written as
$$ N = 2^{a_2} 3^{a_3} \cdots p^{a_p} $$ where the exponents satisfy $a_2 \ge a_3 \ge \ldots \ge a_p\ge 1$. Apart from $4$ and $36$, the last exponent $a_p =1$. Ramanujan's main result concerns the exponents $a_\ell$ for primes $\ell \le p$. He works out detailed estimates for these exponents; roughly they satisfy
$$ a_\ell \approx \frac{1}{\ell^{\alpha}-1}, $$ with $\alpha= \log 2/\log p$, in keeping with the example in Will Sawin's answer.

The numbers produced in Will Sawin's answer are what Ramanujan calls "superior highly composite numbers." These numbers $N$ are characterized by the property that for some $\epsilon >0$ one has $$ \frac{d(N)}{N^{\epsilon}} > \frac{d(n)}{n^{\epsilon}}, $$ for all $n >N$, and $$ \frac{d(N)}{N^{\epsilon}} \ge \frac{d(n)}{n^{\epsilon}} $$ for all $n\le N$. The "superior highly composite numbers" are strictly a subset of the highly composite numbers.

The table on pages 110-112 of Ramanujan's paper lists all the highly composite numbers (with superior highly composite numbers marked with an asterisk) with number of divisors up to $10080$ (that is, Ramanujan computes your $f(n)$ for all $n\le 10078$). Ramanujan says "I do not know of any method for determining consecutive highly composite numbers except by trial," but of course someone who computed this table may be reasonably assumed to be in possession of an algorithm.

Now for the algorithm and its complexity. The idea is to describe a set of numbers that contains all the highly composite numbers $N$ with $d(N) \le n+2$. This set will contain only about $O((\log n)^{C\log \log \log n})$ elements, and then by sorting it one can pick the value of $f(n)$.

We are looking for numbers $N=p_1^{e_1} \cdots p_{k}^{e_k}$ where $p_i$ is the $i$-th prime, and the exponents are in descending order $e_1 \ge e_2 \ge \ldots \ge e_k\ge 1$. Now we can assume that $k\le [\log_2 (n+2)] +1=K$, else $d(N)$ is already larger than $n+2$. Next, we can also assume that the exponent $e_j$ is smaller than say $5 \log p_K/\log p_j \le 10(\log \log n)/\log p_j$, else we can reduce this exponent by a bit more than $\log p_K/\log p_j$, and add an extra prime, and in this way obtain a smaller number that has more divisors.

Now the idea is simply to list all numbers (together with their prime factorizations) that satisfy the above conditions on the exponents. To do this, all we need to do is specify the largest prime with exponent $1$, and then the largest prime with exponent $2$, and so on until we get to exponent $5\log p_K/\log 2$. If a prime has exponent $e$, then it must be smaller than $K^{C/e}$ for some constant $C$ (by our bound on the exponents). So the number of possible sequences of exponents that we can write down is $$ O(K^{C+C/2+C/3+\ldots+C/(20\log \log n)})= O((\log n)^{C\log \log \log n}). $$ That finishes our running time analysis.