Euler came up with following recurrence relation for the sum of divisors (refer to <http://arxiv.org/abs/math/0411587>)
$$\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. I'm wondering how efficient it is to use this method to find a prime, or more specifically to build up all the primes up to a number. It seems pretty fast to add a few numbers, especially the numbers subtracted in the recurrence relation are increasing quadratically?


(I've also asked this question on math.stackexchange: <https://math.stackexchange.com/questions/419059/eulers-sum-of-divisors-recurrence-relation>)



Finding primes using Euler's sum of divisors recurrence relation
Perhaps a summary of the comments is useful. Using Euler's formula for $\sigma(n)$ to test $n$ for primality
certainly is not efficient. The values $\sigma(n-1),\sigma(n-2),\sigma(n-5),\cdots $ are hard to
compute.   

More precisely, in general computing $\sigma(n)$ is equivalent to factoring $n$ in the following sense:


1. Given the factorization of $n$, $\sigma(n)$ can be computed in polynomial time. (This follows immediately from
the formula for $\sigma(n)$, given a prime factorization of $n$).
2. Given $\sigma(n)$, we can produce the factorization of $n$ in random polynomial time. (This has been proved
by Bach, Miller, Shallit 1986).


The AKS-primality test shows that cheking primality can be done in polynomial time. About the growth of $\sigma(n)$, it holds $\lim \sup\_{n\to \infty}\frac{\sigma(n)}{n\log (\log(n))}=e^{\gamma}$, and assuming the Riemann hypothesis,
there is the estimate (Robin) $\sigma(n)< e^{\gamma}n\log(\log(n))$ for all $n\ge 5041$. 


