### M.Mahdi's blog

By M.Mahdi, 5 years ago, , Hi!
Did you know is O(nlogn)? (ω(n) is the number of distinct prime divisors of n) I wonder why! Do you have any mathematical proof for this? math, Comments (8)
 » 5 years ago, # | ← Rev. 2 →   Because 2w(i) ≤ d(i) (d(n) is the number of divisors of n), so this is less than sum of d(i), which is the number of pairs i, j such that j divides i, which is sum of n/j, which is O(nlogn).
•  » » At the first look I was totally surprised about this fact, but it sounds easy when you say it like that! Thanks!
•  » » » it's nice information, do you know any problems that can be solved using it?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   It's one of training tasks for our national OI (INOI): Consider a n × n forest. For each relatively prime pair (i, j)i, j ≤ n, we plant a tree on position (i, j). The problem is to calculate total sum of pairwise distances between trees! n ≤ 106, distance((a, b), (c, d)) = |a - c| + |b - d|Also you can use that fact for this problem.
•  » » » » » I don't think that much theoretically about problem, since each number lower than 10^6 has at most 7 distinct prime divisor, we can perform 2^7 * 10^6 :D This problem is much like SGU 370
•  » » » » » » Yes, but it's always good to know the exact complexity of our solution! (Without considering the limits)
 » 5 years ago, # | ← Rev. 2 →   What about lower bound? I can prove just Ω(nloglogn)
 » 5 years ago, # | ← Rev. 2 →   Lower bound:Let Pn be a set of primes not larger than n. (look here: http://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes). It follows that average number of different primes divisors is , so since 2x is convex we get that it's at least .