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.
Thanks in advance!
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=1748
The link I was talking about: http://terrytao.wordpress.com/2008/09/23/the-divisor-bound/
Is there an efficient solution of the above timus problem without some precalculations and hardcoding?
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.
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).
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.
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.
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 :)
I miss a lot of useful information because I don't know Russian :( why not everybody just write in English?
Maybe because somebody does not know English?
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.
Codeforces sending a lot of duplicate comments lately...
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.