3
$\begingroup$

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)

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 13, 2013 at 18:02
  • $\begingroup$ Then I suppose the sieve methods are a lot more efficient? $\endgroup$ Jun 13, 2013 at 18:05
  • $\begingroup$ Yes, the general number field sieve will be much better. $\endgroup$ Jun 13, 2013 at 18:12
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 13, 2013 at 21:25
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 14, 2013 at 3:47

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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