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)
Best Answer
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:
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$).
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$.