Finding primes using Euler's sum of divisors recurrence relation

Question

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)

Answer 1

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$.

Answer 2

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.