Finding primes using Euler's sum of divisors recurrence relation 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)
 A: 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$. 
A: I agree with everything that's been said about Euler's formula not being a practical way of testing for primality, but it occurs to me there might be special numbers for which it could be useful.  Indulge me in a laborious "proof" that $n=82$ is not a prime.
Euler's formula in this case says
$$\begin{align}
\sigma(82) = &\sigma(81) + \sigma(80) - \sigma(77) - \sigma(75) + \sigma(70) + \sigma(67) - \sigma(60) - \sigma(56)+\cr
&\sigma(47) + \sigma(42) - \sigma(31) -\sigma(25)+\sigma(12)+\sigma(5)\cr
\end{align}$$
As it happens, "most" of the numbers inside the $\sigma$s on the right hand side factor into "small" primes, where by "small" I mean up to $11$.  In particular, we have
$$\begin{align}
\sigma(81)&=\sigma(3^4)=121\cr
\sigma(80)&=\sigma(2^4)\sigma(5)=186\cr
\sigma(77)&=\sigma(7)\sigma(11)=96\cr
\sigma(75)&=\sigma(3)\sigma(5^2)=124\cr
\sigma(70)&=\sigma(2)\sigma(5)\sigma(7)=144\cr
\sigma(60)&=\sigma(2^2)\sigma(3)\sigma(5)=168\cr
\sigma(56)&=\sigma(2^3)\sigma(7)=120\cr
\sigma(42)&=\sigma(2)\sigma(3)\sigma(7)=96\cr
\sigma(25)&=\sigma(5^2)=31\cr
\sigma(12)&=\sigma(2^2)\sigma(3)=28\cr
\sigma(5)&=6\cr
\end{align}$$
When you add and subtract all this stuff up, you have
$$\sigma(82)=42+\sigma(67)+\sigma(47)-\sigma(31)$$
Now we're not allowing ourselves to know that $67$, $47$, and $31$ are primes, but we do know that $\sigma(n)\ge n+1$ for all $n$.  Therefore we have
$$\sigma(82)\ge 42+ 68 + 48 - 32 -\text{stuff} = 126-\text{stuff},$$
where "$\text{stuff}$" is the sum of the divisors (if any) of $31$ other than $1$ and $31$.  These divisors must come in pairs $d,31/d$, with $d$ odd and less than $\sqrt{31}$.  Thus
$$\text{stuff} \le 3+{31\over3}+5+{31\over5} = 24.5333\ldots,$$
and hence
$$\sigma(82) \gt 126-24=112 \gt 83,$$
from which we can conclude that $82$ is not prime.
The obvious drawback to such a "proof" is that it requires an awful lot of computation:  There are always $O(\sqrt n)$ terms to deal with, so its only advantage over trial-and-error division is that you can hope to avoid doing trial divisions by "large" primes.  It also requires a considerable amount of luck -- in this case we were left subtracting the $\sigma$ of only one number that was "too big" to factor, and even it was fairly small.  But still, there might be some rare values of $n$ for which one can deduce something nontrivial from Euler's formula without ever dividing by anything other than "small" primes.
