When is the sum of divisors a prime?

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?

• I don't think you'll have much luck here, with $p=2$ you get the Mersenne primes for example 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. Aug 26 '12 at 6:43

2 Answers

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,

• 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? 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 ! Aug 26 '12 at 11:18

The sum of the 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, the answer to this question is still not known to date.

• Not only powers of two can be candidates, $1 + 3 + 3^2 = 13$ Jun 13 '19 at 12:56