In this post, I write about the divisor number and the Dirichlet Divisor Problem.
First, a short introduction:
Consider an integer number k. You can define divisors of this k easily, i.e. those numbers that can divide k. For instance, if k=6, its divisors are 1, 2, 3, and 6.
It is well-known that there exists a unique prime factorization for this number in the form of (p_1^r_1)*(p_2^r_2)*…*(p_w^r_w). Having this factorization, you can write all divisors as (p_1^a_1)*(p_2^a_2)*…*(p_w^a_w) in which 0<=a_i<=r_i. It is easy to see that there are (r_1 + 1)(r_2 + 1)...(r_w + 1) divisors for the k. Let's call this number d(k).
Well! All these things are high-school number theory. Let's go to something more exciting.
Tonight while I was struggling to solve my algorithms assignments (which was about string matching and those things), the following question came to my mind:
Can I find a bound on the number of divisors of k without knowing its exact factorization? I mean I do not want to factor k to the prime numbers and then solve the problem. I want something in a closed-form which just depends on k as its only variable and not {p_i}s or other things.
Or what about this question: Can I find a bound on the number of the divisors of all number between 1 to n, i.e. a bound for d(1) + d(2) + … + d(n). This is specially important if my intention is calculating the computational complexity of my algorithms which in its i-th step, has an internal loop with d(i) steps (this is exactly what I wanted to do).
I could not solve this problem after trying a bit (the reason: my assignment was already late, I was tired to think about anything else, I am not a number theorist in any case, and more importantly, this problem may not be so easy). Hence, I started searching for a few minutes, and suddenly I found the following result which is named Dirichlet Divisor Problem:
d(1) + … + d(n) = n*ln(n) + (2\gamma – 1) + O(n^\theta)
in which \gamma is Euler-Mascheroni constant. The best estimate of \theta is 7/22 as stated here!
I enjoyed this result. It helped me to replace a O(n^3) by O(n^2*log(n)). 😛 By the way, I suggest you to read Dirichlet Divisor Problem and Divisor Function.