Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
I'll have to disagree with your reasoning since once we have calculated σ. We can use it over and over again. – TurtleTread Jun 13 '13 at 6:09
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. – TurtleTread Jun 13 '13 at 17:45

Your Answer


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.