### M.Mahdi's blog

By M.Mahdi, 8 years ago,

Hi! :)
What is the best upper bound for number of divisors of some natural number n?
I can't find any bound better than :(

• +43

 » 8 years ago, # | ← Rev. 2 →   +14 n^1/3 are often used bound
 » 8 years ago, # | ← Rev. 4 →   +43 As far as I remember, it's . But you can use in practice.UPD: link and discussion on Codeforces (Russian)
 » 8 years ago, # |   +11 T0RRES and yeputons, thank you both!
 » 8 years ago, # |   +60 Regarding the number of divisors, a useful thing for programming contests is to search OEIS for "1344 maximal divisors", or just memorize the sequence numbers for the maximal number of divisors and also the smallest and largest n-digit integers that have the appropriate number of divisors. The two latter sequences are sometimes useful in test cases.The number is 1344 for integers up to 109 and 103 680 for integers up to 1018.
 » 8 years ago, # |   +31 Well, an exact answer is always better than an approximation.http://ideone.com/JNRMsQThis calculates the maximum number of divisors of any positive integer less than n, given n as input. n <= 10^18.Hope this helps.
•  » » 2 years ago, # ^ | ← Rev. 3 →   -18 .
•  » » » 2 years ago, # ^ |   +5 Maximum number of divisors of any positive integer less than n. 72 indeed has 12 divisors
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   -13 .
•  » » » » » 2 years ago, # ^ |   +5 This calculates the maximum number of divisors of any positive integer less than n, given n as input. n <= 10^18.What about this do you not understand?
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   -13 .
 » 2 years ago, # |   +1 I understood why $2\sqrt{n}$ is an upper bound. But can somebody explain the reasoning behind the upper bound being $\mathcal{O}(n^{\frac{1}{3}})$?
•  » » 2 years ago, # ^ |   +39 It's not really true in a way you would expect. That statement with $n^\frac{1}{3}$ should be taken with a grain of salt. It is a mere heuristic that tells you what is more or less the number you could expect if we are talking about numbers that appear within competitive programming, e.g. $\le 10^{18}$. There is no connection between $n^\frac{1}{3}$ and maxium number of divisors other than they are of similar order of magnitude for numbers of that size.