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

Can we efficiently figure out when the sum of divisors of a number can be a prime?

I realized that this can be possible only when the number is expressible as a power of only one prime, e.g. $n = p^\alpha$. Now, the sum of divisors is $ 1+p+p^2+p^3+ \ldots + p^\alpha$. Now the problem is to figure out when this summation could be prime. How do we go about it?

share|cite|improve this question
I don't think you'll have much luck here, with $p=2$ you get the Mersenne primes for example – Cocopuffs Aug 25 '12 at 7:01
And when $\alpha=2$ you're asking for primes of the form $p^2+p+1$, another notorious open problem. – Gerry Myerson Aug 26 '12 at 6:43

This is sequence A023194 of OEIS ($\sigma_1$ is the divisor function).

Not much seems known except that all solutions except $n=2$ may be written as $\ n=p^{2m}$ and have a prime number of divisors (i.e. $2m+1$ is prime).

Sorry if this doesn't help,

share|cite|improve this answer
Thanks, that did help. Am I right in saying that we will not be able to predict in constant time if the sum of the divisors of a number going to be prime or not? – n0nChun Aug 26 '12 at 10:45
@nonChun: since your list includes the Mersenne primes as pointed out by Cocopuffs (see too Gerry's example) you'll need at least a method as efficient as proving primality of these. This doesn't imply that a 'constant time method' doesn't exist but at least that none seems known ! – Raymond Manzoni Aug 26 '12 at 11:18

the sum of divisors of 2^(x-1) is 2^x-1, a Mersenne number. Thus, only powers of two(not all) can be the answer candidates for the question. The well-known Lucas test can be used to verify the primeness of 2^x-1. It has been conjectured that there exist infinitely many Mersenne primes. But, answer to this question is not known till date.

share|cite|improve this answer

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.