# Euler's sum of divisors recurrence relation

Euler came up with following recurrence relation for the sum of divisors $$\sigma(n) = \sigma(n−1) + \sigma(n−2) − \sigma(n−5) − \sigma(n−7) \dots$$

Since $\sigma(p) = p+1$, where $p$ is a prime number, we can use the recurrence relation to verify if a number is prime. It seems fairly fast to add a few numbers, especially the numbers subtracted increase quadratically? I'm wondering how efficient it is to use this method to find a prime, or build all the primes up to a number.

It's recursive. $\sigma(n)$ calls on $\sigma(n-1)$. This means that, in the process of calculating $\sigma(5271009)$ you will have calculated $\sigma(n)$ for every integer $n$ from $1$ to $5271009$. The may be the least efficient known way of determining whether $5271009$ is prime.
• I want to clarify that I mainly want to find a prime by gradually building up this function, and not really to use it for primality testing. But if we have the values of $\sigma$ up to N, it still seems to be a fairly good way to test the primality of N+1. – TurtleTread Jun 13 '13 at 17:45