display | more...
A very handy function in number theory which returns the sum of all positive divisors of a number (including the number itself). σ(1) = 1, σ(2) = 2+1 = 3, σ(6) = 12, σ(220) = 220 + 284 = σ(284), etc.. The sigma function is multiplicative, meaning that if m and n are relatively prime, σ(m*n) = σ(m)*σ(n).

If you don't want to list out every friggin factor of a number n, but still want to find σ(n), there's a cute little formula you can use to find it using the prime factorization of n. I'm going to derive it here. If you don't like proofs, or your browser doesn't show nice little greek charcacters for σ and Π, you'll probably want to skip the next paragraph.

We say that if n can be divided by a prime number p only a times before a rational number is yielded, that p^a is a proper divisor of n, and write:

p^a || n (p prime)
We can thus represent n by writing
Π(p^a || n; p^a)
because this is simply the unique prime factorization of n. Using sigma's multiplicative-ness, we can write that
σ(n) = σ(Π(p^a || n; p^a) = Π(p^a||n; σ(p^a))
Now, for each p,
σ(p^a) = 1 + p + p^2 + p^3 + ... + p^a
which turns out to equal
(p^(a+1) - 1) / (p - 1)
I'm not going to prove that step here, but it's true. So, to find σ(n), we just identify (p^(a+1) - 1) / (p - 1) for each proper divisor p^a of n, and then multiply them all together. Notationally, this is written:
```
-----  p^(a+1) - 1
| |  ------------
| |      p - 1
pa || n```
Bored yet? Here's an exciting example. Suppose some guy comes up to you and offers you \$100 if you can find σ(1200). Using your keen factorization skills, you quickly determine that 1200 = 2^4 * 3 * 5^2. So, you calculate (2^5 - 1)/1 * (3^2 - 1)/2 * (5^3 - 1)/4 = 31 * 4 * 31 = 3844. Hooray! But then it turns out that the guy was just a figment of my imagination, which I temporarily impressed into your consciousness using words.

Words are evil. Words are used to manipulate. Believe in nothing but numbers.

Log in or register to write something here or to contact authors.