The Divisor Function Sigma

January 10, 2014

In number theory, the divisor function σx(n) is the sum of the xth powers of the divisors of n. For instance, the divisors of 60 are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60, so σ0(60) = 12 (the count of the divisors, sometimes called τ(n)), σ1(60) = 168 (the sum of the divisors, sometimes called σ(n) without the subscript), and σ2(60) = 5460. The divisor function is fundamental to much of number theory, and there are many identities and formulas that make use of it, as in the MathWorld article. To calculate the divisor function σx(n), first calculate the prime factorization n =  p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}, then \sigma_x(n) = 1 if n = 1 (regardless of the value of x), \sigma_x(n) = \prod_{i=1}^k (a_i + 1) if x = 0 and \sigma_x(n) = \prod_{i=1}^k \frac{p_i^{(a_i+1)x}-1}{p_i^x-1} if x > 0.

The summatory divisor function calculates the sum of the values of the divisor function from 1 to n; that is \sum_{d=1}^n \sigma_x(n). It could be calculated by summing the values of each of the divisor functions from 1 to n, but a better approach considers for each divisor how many times it appears in the summation: divisor 1 appears for each number from 1 to n, divisor 2 appears for half of them, divisor 3 appears for a third of them, and divisor d appears in ⌊n / d⌋ of them. Arranged in this way, it is easy to calculate the summatory divisor function in linear time.

Your task is to write the divisor and summatory-divisor functions described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

One Response to “The Divisor Function Sigma”

  1. Paul said

    In Python.

    from collections import Counter
    from ma.primee import td_factors
    
    def divisor_sigma(n, x):
        res = 1
        if x  == 0 :
            for pi, ai in Counter(td_factors(n)).iteritems():
                if ai:
                    res *= (ai + 1)
        else:
            for pi, ai in Counter(td_factors(n)).iteritems():
                if ai:
                    res *= (pi ** ((ai + 1) * x) - 1) // (pi ** x - 1)
        return res
        
    def sum_divisor_sigma(n, x):
        if x == 0:
            return sum(n // d for d in xrange(1, n + 1))
        else:
            return sum(n // d * d ** x for d in xrange(1, n + 1))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: