3
$\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?

$\endgroup$
2
  • 6
    $\begingroup$ I don't think you'll have much luck here, with $p=2$ you get the Mersenne primes for example $\endgroup$
    – Cocopuffs
    Aug 25 '12 at 7:01
  • 5
    $\begingroup$ And when $\alpha=2$ you're asking for primes of the form $p^2+p+1$, another notorious open problem. $\endgroup$ Aug 26 '12 at 6:43
3
$\begingroup$

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,

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – n0nChun
    Aug 26 '12 at 10:45
  • $\begingroup$ @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 ! $\endgroup$ Aug 26 '12 at 11:18
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.