4
$\begingroup$

Euler came up with following recurrence relation for the sum of divisors $$\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. It seems fairly fast to add a few numbers, especially the numbers subtracted increase quadratically? I'm wondering how efficient it is to use this method to find a prime, or build all the primes up to a number.

$\endgroup$
2
$\begingroup$

It's recursive. $\sigma(n)$ calls on $\sigma(n-1)$. This means that, in the process of calculating $\sigma(5271009)$ you will have calculated $\sigma(n)$ for every integer $n$ from $1$ to $5271009$. The may be the least efficient known way of determining whether $5271009$ is prime.

$\endgroup$
  • 1
    $\begingroup$ I'll have to disagree with your reasoning since once we have calculated σ. We can use it over and over again. $\endgroup$ – TurtleTread Jun 13 '13 at 6:09
  • 2
    $\begingroup$ I want to clarify that I mainly want to find a prime by gradually building up this function, and not really to use it for primality testing. But if we have the values of $\sigma$ up to N, it still seems to be a fairly good way to test the primality of N+1. $\endgroup$ – TurtleTread Jun 13 '13 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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