The Sigma Function

Definition

σ(n) is the sum of the factors of n.

σ_k(n) is the sum of the n's factors, each to the power k.  So, in particular, σ₀(n), sometimes called τ(n), tau(n), is the number of factors of n.

Working with the Sigma Function

σ(1)=1.

If p is prime then σ(p)=p+1.

If p is prime then σ(pⁿ) = 1 + p + p² + ... + p^k = (pⁿ⁺¹-1)/(p-1).

Put more simply, when n is a power of a prime, p, then σ(n) = (pn-1)/(p-1)

Sigma is a multiplicative function -- that means when a and b are coprime (i.e. GCD(a,b)=1), then σ(ab) = σ(a) σ(b). 

Together, these rules enable you to find the sum of factors of any number, as long as you know its prime factorization.

Example

17640 = 2³ 3² 5 7² 

σ(17640) = (2⁴-1)/(2-1) (3³-1)/(3-1) (5²-1)/(5-1) (7³-1)/(7-1) 

σ(17640) = 15 * 13 * 6 * 57 = 66690

Internet References

Mathworld: Divisor Function 

Related Pages in this website

Totient Function -- the number of coprimes of n.

Highly Composite Numbers -- numbers, n, such that no number smaller than n has as many divisors as n.

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]