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.

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|improve this question
4  
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
3  
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
add comment

1 Answer

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|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
add comment

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.