11
$\begingroup$

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$.

$\endgroup$
9
  • 2
    $\begingroup$ I don't know, but there might be something in the references given at the closely related oeis.org/A002182 $\endgroup$ – Gerry Myerson Oct 27 '17 at 21:13
  • 2
    $\begingroup$ Doesn’t 8 divide 24? $\endgroup$ – Lucia Oct 27 '17 at 21:31
  • 2
    $\begingroup$ I don't understand why you say that $f(100) = 2949120$. Isn't $f(100)=50400$? $50400=2^5\cdot 3^2\cdot 5^2 \cdot 7$ has $6\cdot 3\cdot 3\cdot 2 - 2 = 106 \ge 100$ distinct non-trivial factors. $\endgroup$ – Timothy Chow Oct 28 '17 at 3:40
  • 3
    $\begingroup$ Timothy Chow is right, and again this is in Ramanujan's paper. Ramanujan also knew that (in your notation) $f(10000)= 6746328388800$. See ramanujan.sirinudi.org/Volumes/published/ram15.pdf $\endgroup$ – Lucia Oct 28 '17 at 4:06
  • 2
    $\begingroup$ Needless to say, the fact that we can compute $f(10^{1254})$ suggests strongly that the true complexity of computing $f(n)$ is not polynomial in $n$, but rather polynomial in $\log n$. $\endgroup$ – shreevatsa Oct 30 '17 at 20:43
13
$\begingroup$

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.


          Ramanujan
          The beginning of Ramanujan's table.


$\endgroup$
11
  • $\begingroup$ Wonderful that Ramanujan computed these numbers a century ago! I took the liberty of adding the start of his table. $\endgroup$ – Joseph O'Rourke Oct 30 '17 at 11:01
  • $\begingroup$ Thanks for finding the relevant literature. I believe you have misread my answer, and it is in fact accurate. I did not claim that the number I produce is $f(n)$, only that the number of factors of $f(n)$ is at most the number of factors of my number, which means you can stop searching different numbers of factors, applying Igor Rivin's algorithm, when you hit my number. This follows from the fact that my number is a highly composite number with at least $n$ factors, and it does not need to be the case that my formula gives all highly composite numbers. $\endgroup$ – Will Sawin Oct 30 '17 at 13:53
  • $\begingroup$ @WillSawin: Thanks! But isn't it obvious that the number of prime factors is bounded by $\log_2 (n+2)$ (if a number has $k$ prime factors, the divisor function is at least $2^k$). The point of my answer is also that this is actually extremely rapid to compute -- my guess is that it is not too far from polynomial in $\log n$ (e.g $\exp((\log \log n)^2)$ or something like that might be enough). $\endgroup$ – Lucia Oct 30 '17 at 14:16
  • $\begingroup$ @Lucia I was trying to bound the number of divisors of the smallest number with at least $n$ divisors. Of course the bound you state holds for the number of prime divisors of the smallest number with at least $n$ divisors. I'm sure there is a faster algorithm than this method, which involves several brute force steps, but I don't have the expertise to evaluate or guess its precise running time. $\endgroup$ – Will Sawin Oct 30 '17 at 15:00
  • 1
    $\begingroup$ @shreevastava: The numbers involved are not very big. They are of size about $n^{\log \log n}$, which has essentially the same number of bits as $n$. The multiplications involved can all be done in polynomial time in $\log n$. $\endgroup$ – Lucia Nov 15 '17 at 3:17
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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$.

$\endgroup$
1
5
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ It's worse than this, because one can't only look at $n$; as the $n=100$ case illustrates, there may be 'easier' values (ones that lead to smaller $f(n)$ slightly larger than $n$ (those specifically that have fewer factors, or more specifically that have 'weightedly fewer' factors for an appropriate weighting). So one has to search a potentially indeterminate distance above $n$. $\endgroup$ – Steven Stadnicki Oct 27 '17 at 22:15
  • 1
    $\begingroup$ @StevenStadnicki: "So one has to search a potentially indeterminate distance above $n$." This is exactly my dilemma. Thank you for articulating it. $\endgroup$ – Joseph O'Rourke Oct 27 '17 at 22:32
  • $\begingroup$ @StevenStadnicki Yes, you are right, I am answering the question of finding the smallest $n$ with a given number of divisors. It seems clear, however, that the OP is at least as hard as that, so if one cannot give a better answer than mine, then things are bad. $\endgroup$ – Igor Rivin Oct 28 '17 at 3:37
  • 2
    $\begingroup$ @IgorRivin : It's not clear to me that the original question is at least as hard as your problem. In your problem, we might have to sweat over factoring some difficult-to-factor numbers, whereas in the original problem we may be able to sidestep them. $\endgroup$ – Timothy Chow Oct 28 '17 at 4:28
  • $\begingroup$ The question is much easier than factoring IMO. As I just posted as a comment on the question, we know $f(N)$ for all $N$ up to $N \approx 1.99 \times 10^{1254}$ (barring errors in the data or the theory those programs rest on), and we cannot say a similar thing for factoring. $\endgroup$ – shreevatsa Oct 30 '17 at 18:14

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.