### Enchom's blog

By Enchom, 10 years ago,

Hello everybody,

Lately I've solved a few problems that include the number of divisors of N in their complexity. Now I'm a person that loves to know exactly the complexity of his algorithms so I tried to look around the web for the values and I read from wikipedia the Divisor Function page, but I couldn't find what I'm looking for (it might've been there, I had tough time understanding most of their explanations).

So suppose D(n) is the number of divisors of n. I'm looking for a good bound on D(n) expressed using n.

Note that it is very easy to see and prove that D(n)<2*sqrt(n), but I did some tests and I believe a stronger (not much stronger but still stronger) bound should exist. Sorry if the answer is already described somewhere online, I had tough time finding it.

• +12

 » 10 years ago, # | ← Rev. 3 →   +16 I've posted a link about the topic. Basically, what I took from this article and my previous experience is that the bounds for D(N) are usually useless in programming contests because the constants involved are really unclear. I usually make do with the fact that on average N has log(N) divisors and memorizing D(N) for a few landmark highly-composite numbers such as:A number less than 10 ^ 12 will have at most 7000 divisors, less than 10 ^ 18 up to 100000 divisors. There's actually a problem on TIMUS that I've solved and I occasionally use the code to get the maximum D(x) for some x <= N.http://acm.timus.ru/problem.aspx?space=1&num=1748The link I was talking about: http://terrytao.wordpress.com/2008/09/23/the-divisor-bound/
•  » » 10 years ago, # ^ |   0 Is there an efficient solution of the above timus problem without some precalculations and hardcoding?
•  » » » 10 years ago, # ^ |   0 DP best[i][j] = minimal number with primes up to i-th in it's factorization and exactly j divisors fits into TL — you just have to try all possibilities for degree of next prime.
•  » » » 10 years ago, # ^ | ← Rev. 2 →   0 Yes, there is. I do not know how exactly efficient it is, because it is recursive brute-force with obvious pruning (it is my solution, there are probably better solutions).
•  » » » 10 years ago, # ^ |   +1 Yes, a smart brute force runs instantly on any test case. I think it had something like 40 000 states. Also a good number to know.
 » 10 years ago, # |   +40 Briefly, you can use N^(1/3) for rought approximation of D(N) while solving problems. And theoretical bound is much better — D(N) is actually sub-polynomial. It is mentioned even in Wikipedia:) And this question was discussed many times in russian part of Codeforces, you may take a look at topics like this and this.
•  » » 10 years ago, # ^ | ← Rev. 3 →   +3 I did some tests and wow, N^(1/3) seems like a nice approximation for complexity purposes, I didn't know that. Turns out there is way stronger bound than 2*sqrt(n), and I've always thought it's not that far from that.Thanks a lot :)
•  » » 10 years ago, # ^ |   +43 I miss a lot of useful information because I don't know Russian :( why not everybody just write in English?
•  » » » 10 years ago, # ^ |   0 Maybe because somebody does not know English?
 » 10 years ago, # |   +23 When I need to look this up for a problem, I usually use a cheat table: http://wwwhomes.uni-bielefeld.de/achim/highly.txt. You can memorize some common bounds from there as well if you feel so inclined.If you're looking at the number of divisors of a lot of different numbers, then you should know that it's log(n) on average.
 » 10 years ago, # | ← Rev. 2 →   +16 Codeforces sending a lot of duplicate comments lately...
 » 10 years ago, # |   0 There has been a discussion in russian threads a few years ago: http://mirror.codeforces.com/blog/entry/651, http://mirror.codeforces.com/blog/entry/3863.