5
$\begingroup$

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?

  • 5
    And when $\alpha=2$ you're asking for primes of the form $p^2+p+1$, another notorious open problem.2012-08-26

2 Answers 2

4

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,

  • 0
    @nonChun: since your lis$t$ includes the [Mersenne primes](http://en.wikipedia.org/wiki/Mersenne_prime) as pointed out by Cocopu$f$fs (see too Gerry's ex$a$mple) 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 !2012-08-26
1

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.