Computational complexity of finding the smallest number with n factors

Question

Given $n \in \mathbb{N}$, suppose we seek the smallest number $f(n)$ with at least $n$ distinct factors, excluding $1$ and $n$. For example, for $n=6$, $f(6)=24$, because $24$ has the $6$ distinct factors $\{2,3,4,6,8,12\}$, and $24$ is the smallest integer with $6$ factors.

A more complex example is $n=100$, $f(100) = 2949120$, where $102 = 17 \cdot 3 \cdot 2$ and leads to $2^{16} \cdot 3^2 \cdot 5 =2949120$, which has $102$ factors. Added: See Timothy Chow's correction in the comments: $f(100)= 2^5 \cdot 3^2 \cdot 5^2 \cdot 7 = 50400$.

All this is known; the sequence is OEIS A061799. E.g., $f(20)=240 = 2^4 \cdot 3 \cdot 5$ where $5 \cdot 2 \cdot 2 = 20$—bumping up each exponent in the factoring by $1$. My question is:

Q. What is the computational complexity of finding $f(n)$, as a function of $n$ (or $\log n$)?

Is this known?

---

Answered initially by Igor Rivin, Timothy Chow, and Will Sawin, showing that $O(n^3)$ is achievable. Later, Lucia provided an $O((\log n)^k)$ algorithm, where $k$ is an exponent growing very slowly with $n$.

Answer 1

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.

---

         
          ^{The beginning of Ramanujan's table.}

---

Answer 2

This is not a complete answer but it describes an algorithm for computing $f(n)$ that should be reasonably fast. Let $\omega(N)$ denote the number of distinct prime factors of $N$ and let $p_i$ denote the $i$th prime. If we happen to know the value of $\omega(f(n))$—call it $k$—then we can find $f(n)$ by solving the following convex optimization problem with a linear objective function:

Minimize $\sum_{i=1}^k x_k \log p_k$ subject to the constraint $\prod_{i=1}^k (1+x_i) \ge n + 2$,

where the $x_i$ are required to be positive integers. The value of $f(n)$ will then be $\prod_{i=1}^k p_i^{x_i}$. Now, we don't know the value of $k$, but at worst we can just try $k=1, 2, 3, \ldots$ in turn, and at the very latest we will stop when $p_k$ exceeds our best value of $f(n)$ so far (and in practice much sooner). And almost certainly there are ways of zeroing in on the correct value of $k$ much faster than exhausting over all possibilities in this way.

Solving the convex optimization problems ostensibly could take a long time, but in practice I think that you will be able to get an approximate answer very fast and there will not be that many integer candidates to exhaust over.

Answer 3

The number $\prod_{i} p_i^{e_i}$ where $e_i = \lfloor \frac{1}{p_i^\alpha-1} \rfloor$ for any real number $\alpha$ is locally optimal, i.e. no smaller number has a larger product of factors. (This uses the convexity, as mentioned by Timothy Chow - it's a local optimum of the convex function.) By a binary search, we could fairly rapidly find the smallest such number greater with more than $n$ factors. Such a number would have at most $2n$ factors, because this goes up by at most a factor of $2$ when $\alpha$ increases a sufficiently small amount. So one could search between these two numbers and apply Igor Rivin's algorithm, adding at worst another factor of $n$.

Answer 4

The number of divisors of $n = \prod_{i=1}^k p_i^{\alpha_i}$ is $g(n)=\prod_{i=1}^k (1+\alpha_i)$ (your function differs from this by $2.$) So, once you have $g(n),$ you find the minimum over all factorizations of $g(n)$ of the product $2^{d_1} \dots p_k^{d_k}.$ Now, the number of factorizations of $N$ is $o(g(n)^2)$ - by a result of Canfield, Erdos, Pomerance

Canfield, E.R.; Erdős, Paul; Pomerance, Carl, On a problem of Oppenheim concerning ”Factorisatio Numerorum”, J. Number Theory 17, 1-28 (1983). ZBL0513.10043.

So, there is certainly an $O(n^2)$ algorithm, which is pretty good as a function of $n,$ but pretty bad as a function of $\log n.$ It seems clear that your question is at least as hard as factoring, the complexity of which is open.

By the way, I learned of the CEP paper from

Balasubramanian, Ramachandran; Luca, Florian, On the number of factorizations of an integer, Integers 11, No. 2, 139-143, A12 (2011). ZBL1245.11100.