Enchom's blog

Amount of divisors of N
By Enchom, 10 years ago, In English

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!

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

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/

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there an efficient solution of the above timus problem without some precalculations and hardcoding?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
»
10 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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 :)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    I miss a lot of useful information because I don't know Russian :( why not everybody just write in English?

    → Reply
»
10 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Codeforces sending a lot of duplicate comments lately...

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There has been a discussion in russian threads a few years ago: http://codeforces.me/blog/entry/651, http://codeforces.me/blog/entry/3863.

→ Reply