Prime Sum of Divisors

Surprisingly, for me at least, there are not many numbers whose sum of divisors is prime. However, the number associated with my diurnal age today, \( \textbf{27889}\), is one such number. The numbers up to 40000 are 2, 4, 9, 16, 25, 64, 289, 729, 1681, 2401, 3481, 4096, 5041, 7921, 10201, 15625, 17161, 27889, 28561 and 29929. These are the initial terms of OEIS A023194. Here is the breakdown (with 2 excluded - permalink):

number   square root   sigma

  4        2             7

  9        3             13

  16       4             31

  25       5             31

  64       8             127

  289      17            307

  729      27            1093

  1681     41            1723

  2401     49            2801

  3481     59            3541

  4096     64            8191

  5041     71            5113

  7921     89            8011

  10201    101           10303

  15625    125           19531

  17161    131           17293

  27889    167           28057

  28561    169           30941

  29929    173           30103

The members of this sequence are all square numbers with the exception of 2. Some are powers of 2 as well such as 16, 64 and 4096. The OEIS comments contain the following observations (that I'm not sure I understand):

All terms except the first are squares. Why? 

 

Answer from Gabe Cunningham (gcasey@mit.edu): "From the fact that the sigma (the sum-of-divisors function) is multiplicative, we can derive that the \( \sigma(n)\) is even except when \(n\) is a square or twice a square. 

 

"If \(n = 2 \times (2 \times k + 1)^2\), that is, \(n\) is twice an odd square, then:$$ \sigma(n) = 3 \times \sigma((2 \times k + 1)^2)$$If \(n = 2 \times (2 \times k)^2 \), that is, \(n\) is twice an even square, then \( \sigma(n)\) is only prime if \(n\) is a power of 2; otherwise we have:$$ \sigma(n) = \sigma(8 \times 2^m) \times \sigma(k/2^m)$$ for some positive integer \(m\). 

 

"So the only possible candidates for values of n other than squares such that \( \sigma(n)\) is prime are odd powers of 2. But:$$ \begin{align} \sigma(2^{(2 \times m + 1)}) &= 2^{(2 \times m + 2)} - 1 \\ &= (2^{m + 1} + 1) \times (2^{m + 1 }- 1) \end{align}$$which is only prime when \(m = 0\), that is, when \(n = 2\). So 2 is the only nonsquare \(n\) such that \( \sigma(n)\) is prime."

I looked to Gemini to explain what the above means by asking the following question;

What does it mean to say that "the sigma function is multiplicative" where sigma is the sum of divisors function? The fuller quote is as follows: 

... I just included the quote above ...

The quote is taken from the comments to OEIS A023194 (https://oeis.org/A023194). Can you break this down for me as I simply don't understand what the author is on about?

Here was the response (link):

Of course. Let's break down this number theory argument step by step. It's a great example of how a single property of a function can lead to a powerful conclusion.

What does "Multiplicative" Mean?

First, let's tackle the main concept. In number theory, a function f(n) is called multiplicative if, for any two coprime integers a and b, the following equation holds true:

f(a * b) = f(a) * f(b)

Coprime means that the two numbers share no common factors other than 1. For example, 4 and 9 are coprime, but 6 and 9 are not (they share a common factor of 3).

The sigma function, written as σ(n), calculates the sum of all the positive divisors of a number n.

Let's test the multiplicative property with an example, n = 12.

We can split 12 into the coprime factors 3 and 4.

• σ(12): The divisors of 12 are 1, 2, 3, 4, 6, and 12. Their sum is 1 + 2 + 3 + 4 + 6 + 12 = 28.

• σ(3): The divisors of 3 are 1 and 3. Their sum is 1 + 3 = 4.

• σ(4): The divisors of 4 are 1, 2, and 4. Their sum is 1 + 2 + 4 = 7.

Now let's check if the property holds:

σ(3) * σ(4) = 4 * 7 = 28

It works! σ(12) = σ(3) * σ(4). This property is incredibly useful because it allows us to find σ(n) by first finding the prime factorization of n. If n = p₁^a₁ * p₂^a₂ * ..., then σ(n) = σ(p₁^a₁) * σ(p₂^a₂) * ....

---

Deconstructing the Argument

Now, let's walk through the author's logic for finding the non-square numbers n where σ(n) is prime. The goal is to eliminate all possibilities until only one remains.

Part 1: When is σ(n) an odd number?

The author starts with the fact that σ(n) is almost always even. For σ(n) to be a prime number (other than 2), it must be an odd prime. So, when is σ(n) odd?

σ(n) is odd only if all the factors in its prime decomposition, σ(p₁^a₁), σ(p₂^a₂), ..., are also odd.

• For powers of 2 (p=2): σ(2^a) = 1 + 2 + 4 + ... + 2^a = 2^(a+1) - 1. This sum is always odd. (e.g., σ(4) = 7, σ(8) = 15).⁶

• For powers of an odd prime (p is odd): σ(p^a) = 1 + p + p² + ... + p^a. This sum of numbers is odd only if there is an odd number of terms. The number of terms is a+1. For a+1 to be odd, a must be even.

So, for σ(n) to be odd, any odd prime factor in n must have an even exponent. This means n must be of the form:

n = 2^k * (an odd number that is a perfect square)

This leads to two cases:

1. k is even: n is a perfect square (e.g., 2² * 3² = 6²).

2. k is odd: n is twice a perfect square (e.g., 2³ * 5² = 2 * (2*5)² = 2 * 10²).

The author states: σ(n) is odd only when n is a square or twice a square. This is the conclusion. Since we are looking for non-square values of n, this immediately tells us we only need to check numbers that are twice a square.

Part 2: Analyzing n as "Twice a Square"

We've narrowed our search to n = 2k². The author now splits this into two sub-cases based on whether k is odd or even.

• Case A: n is twice an odd square. (n = 2 * m², where m is odd).

  Since 2 and m² are coprime, we can use the multiplicative property:

  σ(n) = σ(2 * m²) = σ(2) * σ(m²) = 3 * σ(m²)

  For this result (3 * σ(m²)) to be a prime number, it must be equal to 3. This is only possible if σ(m²) = 1. The only number whose sum of divisors is 1 is the number 1 itself. So m² = 1, which means m = 1.

  This gives us our first candidate: n = 2 * 1² = 2.

  Let's check: σ(2) = 1 + 2 = 3, which is a prime number. And n=2 is not a square. So, 2 is a solution.

• Case B: n is twice an even square. (n = 2 * m², where m is even).

  Let the even number m = 2^j * s, where s is an odd number and j ≥ 1.

  Then n = 2 * (2^j * s)² = 2 * 2^(2j) * s² = 2^(2j+1) * s².

  This n is composed of an odd power of 2 (2^(2j+1)) and an odd square (s²). These two parts are coprime.

  σ(n) = σ(2^(2j+1)) * σ(s²)

  As we established, both σ(power of 2) and σ(odd square) are odd numbers greater than 1 (assuming s > 1). When you multiply two integers that are both greater than 1, the result is a composite (non-prime) number.

  Therefore, for σ(n) to have any chance of being prime, the s² part must not exist. This means s must be 1.

Part 3: The Final Elimination

The previous step forces us to conclude that the only possible candidates left are when s=1. This means n must be an odd power of 2.

n = 2^(2m+1) for m ≥ 0.

Let's find the sigma of this number:

σ(n) = σ(2^(2m+1)) = 2^((2m+1)+1) - 1 = 2^(2m+2) - 1

The author then uses a standard algebraic factorization for a difference of squares (a² - b² = (a-b)(a+b)):

2^(2m+2) - 1 = (2^(m+1))² - 1² = (2^(m+1) - 1) * (2^(m+1) + 1)

For this product to be a prime number, one of its factors must be equal to 1.

• The second factor, (2^(m+1) + 1), is clearly larger than 1.

• Therefore, the first factor must be 1:

  2^(m+1) - 1 = 1

  2^(m+1) = 2

  m+1 = 1

  m = 0

Plugging m=0 back into our formula for n:

n = 2^(2*0 + 1) = 2¹ = 2.

This confirms that the only possible candidate that survived this entire process of elimination is the number 2.

Summary

The author brilliantly uses the multiplicative nature of σ(n) to prove that 2 is the only non-square number whose sum of divisors is a prime number. 

I'm not sure I'm any the wiser but we definitely all such numbers are squares!

Anyway, by contrast, numbers for which the sum of the \( \textbf{proper}\) divisors is prime are far more common. There are 3771 of them in the range up to 40000.