From 1 to n, count how many integers there are with the sum of divisors being a prime number? [closed]

Besides 2, only even-exponent prime-powers can have the desired property.

Quick start: the sum of divisors of a number with prime factors p_i and their exponents α_i is

and we want this product to be prime (image from MathWorld). So we can't have more than one prime factor.

Let's say we're looking at the number x·7² with x not divisible by 7. Then the divisors are the divisors of x, and the same divisors each multiplied by 7, and the same divisors multiplied by 49. Their sum is thus 1+7+49 times the sum of the divisors of x. If the latter is larger than 1, that's not prime.

So you can't combine prime factor 7 with any other. And likewise you can't combine any different prime factors. We only need to consider prime powers.

Also, except for 2¹, the prime power needs to have an even exponent. Otherwise, for example for 3⁵ the sum of divisors is 1+3+9+27+81+243 = (1+3)+(9+27)+(81+243) = 1*4 + 9*4 + 81*4 = (1+9+81)*4. That's some multiplier times (1+thePrime). And even if the multiplier is 1, the (1+thePrime) is only a prime for thePrime=2.

So: Besides 2, the only good numbers are even-exponent prime-powers. And their sum of divisors (sod) is also easy to calculate.

Python code taking half a second to find the 310 numbers that lastchance also found:

from math import isqrt

N = 10**9

def isprime(n):
  return all(n%d for d in range(2, isqrt(n)+1))

good = {2}
for i in range(2, isqrt(N)+1):
  if isprime(i):
    e = 2
    while i**e <= N:
      sod = (i**(e+1) - 1) // (i - 1)
      if isprime(sod):
        good.add(i**e)
      e += 2

print(len(good))
print(*sorted(good))

Shortened output (Attempt This Online!):

310
2 4 9 16 25 (...) 978250729 982007569 984641641

C++ code, also prints 310:

#include <iostream>

bool isprime(int n) {
  for (int d=2; d<=n/d; d++)
    if (n%d == 0)
      return false;
  return true;
}

int main() {
  int n = 1'000'000'000;
  int good = 1;
  for (int i=2; i<=n/i; i++) {
    if (isprime(i)) {
      for (long long I = i*i; I <= n; I *= i*i) {
        long long sod = (I*i-1) / (i-1);
        good += isprime(sod);
      }
    }
  }
  std::cout << good << '\n';
}

Attempt This Online!

If the number is odd then divisors pair off (to make an even sum) unless the central divisor is repeated (i.e. the number is square).

If the number is even then take out factors of 2 until it is odd. Then the number is of the form ODD.2^r. The divisors of the odd number are as above, so will only produce an odd sum if it is square. Multipliers of 2 will not change the oddness or even-ness of the sum. If r is even then we are again checking a square. If r is odd then we check 2 times a square.

The following for N=1000'000'000. I believe that there are 310 such numbers (all squares, except 2). Probably someone can come up with a better idea for the even-number tests.

#include <iostream>
#include <cmath>
using namespace std;

using INT = unsigned long long;

//======================================================================

INT sumDivisors( INT num )
{
   INT sum = 1;
   if ( num != 1 ) sum += num;

   INT imax = sqrt( num + 0.5 );       // divisors come in pairs
   for ( INT i = 2; i <= imax; i++ )
   {
      if ( num % i == 0 )
      {
         INT ii = num / i;             // second divisor
         sum += i;
         if ( ii != i ) sum += ii;
      }
   }
   return sum;
}

//======================================================================

bool isPrime( INT n )
{
   if ( n < 2      ) return false;
   if ( n % 2 == 0 ) return n == 2;

   INT imax = sqrt( n + 0.5 );
   for ( INT i = 3; i <= imax; i += 2 )
   {
      if ( n % i == 0 ) return false;
   }
   return true;
}

//======================================================================

int main()
{
   INT counter = 0;
   INT N = 1000'000'000;
   for ( INT s = 1; s <= sqrt( N + 0.5 ); s++ )
   {
      INT i = s * s;                                       // test squares
      INT S = sumDivisors( i );
      if ( isPrime( S ) )
      {
         cout << i << ": " << S << '\n';
         counter++;
      }

      i = 2 * s * s;                                       // test twice a square
      if ( i > N ) continue;
      S = sumDivisors( i );
      if ( isPrime( S ) )
      {
         cout << "Additional " << i << ": " << S << '\n';
         counter++;
      }
   }
   cout << counter << '\n';
}

Output (final answer - at the bottom - 310)

Additional 2: 3
4: 7
9: 13
16: 31
25: 31
...
...
978250729: 978282007
982007569: 982038907
984641641: 984673021
310

When you do not know whether the sum is prime or not, then you need to actually compute it.

However, there are general ideas that you can apply, such as:

• if the sum has a pair amount of odd divisor types, then it's divisible with two, hence you do not need to check whether it's prime, you'll instantly know whether it's prime (equals 2) or not

Such ideas can be applied to drastically reduce the number of sums whose prime-ness you are to check. If such quickening rules fail to determine for a sum whether it's prime, then you will need to do the costly prime calculation, but it would be a much rarer necessity, than without these pre-filters.