Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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

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.