Sum of number of divisor of number between a and b inclusive

Question

Let there be a function g(x)=number of divisor of x. Given two integers a and b we need to find->

g(a)+g(a+1)....+g(b).

I thought this step->

for every x from a to b

sum+=number of divisor of x(in sqrt(x) complexity)

but its given 1<=a<=b<=2^31-1

So to iterate between a and b can cost me a lot of time....for eg->if a=1 and b=2^31-1.

Is there a better way to do?

Answer 1

Here's some simple but reasonably efficient Python code that does the job.

import math

def T(n):
    "Return sum_{i=1}^n d(i), where d(i) is the number of divisors of i."
    f = int(math.floor(math.sqrt(n)))
    return 2 * sum(n // x for x in range(1, f+1)) - f**2

def count_divisors(a, b):
    "Return sum_{i=a}^b d(i), where d(i) is the number of divisors of i."
    return T(b) - T(a-1)

Explanation: it's enough to be able to compute the sum from 1 to b, then we can do two separate computations and subtract to get the sum from a to b. Finding the sum of the divisor function from 1 to b amounts to computing sequence A006218 from the online encyclopaedia of integer sequences. That sequence is equivalent to the sum of floor(n / d) as d ranges over all integers from 1 to n.

And now that sequence can be thought of as the number of integer-valued points under the hyperbola xy=n. We can use the symmetry of the hyperbola around the line x = y, and count the integer points with x <= sqrt(n) and those with y <= sqrt(n). That ends up double counting the points with both x and y less than sqrt(n), so we subtract the square of floor(sqrt(n)) to compensate. All this is explained (briefly) in the introduction to this paper.

Remarks:

• the algorithm has running time O(sqrt(b)), and constant space requirements. Improvements in running time are possible at the expense of space; see the paper referred to above.

• for really large n, you'll want a proper integer square root rather than using floor(math.sqrt(n)), to avoid problems with floating-point inaccuracies. That's not a problem with the sort of n that you're looking at. With typical IEEE 754 floating-point and a correctly rounded square root operation, you're not going to run into trouble until n exceeds 2**52.

• if a and b are really close, there may be more efficient solutions.

Answer 2

Because the desired result is the total number of divisors for all the numbers in a range, there's no need to count divisors of individual numbers in the range; instead, count the number of times 1 is a divisor, 2 is a divisor, etc. This is an O(b) computation.

That is, add up b-(a-1), b/2 - (a-1)/2, b/3 - (a-1)/3, etc. .

In the python code shown below (which uses python operator // for integer division with truncation) divisors from 2 to about b/2 are counted using a for loop. Note that divisors that are smaller than b but larger than max(a, b/2) occur once each and need not be counted in a loop. The code uses the expression b-max(a,(b+1)//2+1)+1 to count them. Output is shown after the program.

When k different a,b sets are to be treated, it is possible to compute all the answers in time O(k+bₘₐₓ) where bₘₐₓ is the largest value of b.

Python code:

def countdivisors(a,b):
    mid = (b+1)//2+1
    count = b-a+1 +b-max(a,mid)+1 # Count for d=1 & d=n
    for d in xrange(2,mid):
        count += b//d - (a-1)//d
    return count
# Test it:
a=7
for b in range(a,a+16):
    print '{:3} {:3} : {:5}'.format(a, b, countdivisors(a,b))

Output:

  7   7 :     2
  7   8 :     6
  7   9 :     9
  7  10 :    13
  7  11 :    15
  7  12 :    21
  7  13 :    23
  7  14 :    27
  7  15 :    31
  7  16 :    36
  7  17 :    38
  7  18 :    44
  7  19 :    46
  7  20 :    52
  7  21 :    56
  7  22 :    60