Блог пользователя Enchom

Автор Enchom, 10 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
10 лет назад, # |
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=1748

The link I was talking about: http://terrytao.wordpress.com/2008/09/23/the-divisor-bound/

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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 лет назад, # ^ |
      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 лет назад, # ^ |
        Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится +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 лет назад, # ^ |
    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 лет назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +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 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Codeforces sending a lot of duplicate comments lately...

»
10 лет назад, # |
  Проголосовать: нравится 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.