Timeline for Computational complexity of finding the smallest number with n factors
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15, 2017 at 4:54 | comment | added | shreevatsa | @Lucia Great, thanks for adding that. | |
| Nov 15, 2017 at 3:17 | comment | added | Lucia | @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$. | |
| Nov 15, 2017 at 3:03 | comment | added | shreevatsa | To finish the running time analysis, we also need to consider the cost of comparing the numbers themselves: we cannot compare (or sort) arbitrarily large numbers in constant time. The time it takes depends on the sizes of the actual numbers we're comparing, and in this case they're considerable. | |
| Nov 14, 2017 at 23:16 | comment | added | shreevatsa | @MarianoSuárez-Álvarez The paper does not contain ten thousand items. It contains the first 103 (if I have counted correctly), and because the item $6746328388800$ has $10080$ divisors, we know $f(n)$ (for the $f$ in the question) for all $n \le 10078$. (That's the point being made: the problem is easy relative to the size of $n$, because we only need to compute a small number of Highly-Composite Numbers.) Why did Ramanujan stop after $103$ items rather than a rounder number? I guess he stopped when $d(N)$ exceeded 10000. | |
| Nov 4, 2017 at 17:37 | comment | added | Gerhard Paseman | Probably a page limitation. Gerhard "Otherwise It Looks Like Padding" Paseman, 2017.11.04. | |
| Nov 4, 2017 at 17:01 | comment | added | Mariano Suárez-Álvarez | Is there an indication of why he stopped at 10080 and not a rounder number? | |
| Nov 4, 2017 at 16:59 | comment | added | Mariano Suárez-Álvarez | The paper has a table with ten thousand items?! | |
| Nov 4, 2017 at 16:48 | vote | accept | Joseph O'Rourke | ||
| Nov 4, 2017 at 16:33 | history | edited | Lucia | CC BY-SA 3.0 |
added 1680 characters in body
|
| Oct 30, 2017 at 15:00 | comment | added | Will Sawin | @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. | |
| Oct 30, 2017 at 14:16 | comment | added | Lucia | @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). | |
| Oct 30, 2017 at 13:53 | comment | added | Will Sawin | 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. | |
| Oct 30, 2017 at 11:01 | comment | added | Joseph O'Rourke | Wonderful that Ramanujan computed these numbers a century ago! I took the liberty of adding the start of his table. | |
| Oct 30, 2017 at 11:00 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 220 characters in body
|
| Oct 30, 2017 at 1:48 | history | answered | Lucia | CC BY-SA 3.0 |