Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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: http://math.stackexchange.com/questions/419059/eulers-sum-of-divisors-recurrence-relation)

share|improve this question
1  
We would need a lot of values $\sigma(j)$ for larger $j$. Try to do it , say, for $n=2^{9941}-1$ with your computer. –  Dietrich Burde Jun 13 '13 at 18:02
    
Then I suppose the sieve methods are a lot more efficient? –  Kayu Jun 13 '13 at 18:05
    
Yes, the general number field sieve will be much better. –  Dietrich Burde Jun 13 '13 at 18:12
1  
If this formula would have been efficient to find primes, then no doubt Euler would have known about it -- even if there was no computer at the time. –  François Brunault Jun 13 '13 at 21:25
1  
Kayu, "add a few numbers"? Sure, but first you have to calculate those numbers. You can't calculate $\sigma(n-1)$ without factoring $n-1$, and factoring $n-1$ is likely to be harder than using, say, APR to test $n$ for primality, so even calculating the first number in your sum is likely to be highly inefficient as part of a primality test. –  Gerry Myerson Jun 14 '13 at 3:47

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
That was very fun to read. Thanks! –  Kayu Jun 15 '13 at 1:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.