# Sum of divisors - Relations

Let N = ∏pm the prime factorization of N. We get divisors of N by choosing exponents between 0 and m for each prime factor p, in all possible ways. The number of divisors, 1 and N included, is then :

∏(m+1)

For instance 600 = 23×3×52 has (3+1)(1+1)(2+1) = 24 divisors.
By expanding the product ∏p (∑i pi), for which in every sum ∑ : 0 ≤ i ≤ m for that prime p, we get every term of expansion by choosing an exponent for each prime factor p.
Hence it is a divisor of N and the sum is the sum of divisors of N, as we get all of them.
∑pi can be written (pm+1-1)/(p-1) as sum of a geometric series, and finally :

S = ∏p (∑i pi) = ∏(pm+1-1)/(p-1)

For instance N = 600 : S = (1+2+4+8)(1+3)(1+5+25) = (16-1) × (9-1)/2 × (125-1)/4 = 1860

Script for calculation of sum of divisors

Let's speak now about perfect numbers. The odd perfect numbers are unknown, and we think there are none. However if there is one, it is more than 300 digits ! On the contrary, even perfect numbers are known since Euclid, and Euler proved they are all :

2(p-1)(2p-1) with 2p-1 being prime

The number 2p-1 is not prime for every exponent p.
p must be prime, but it is not sufficient, for instance 211-1 = 2047 = 23x89.
Numbers Mp = 2p-1 are primes (Mersenne primes) for p = 2, 3, 5, 7, 13, 17, 19, 31...
That is Mersenne primes 3, 7, 31, 127, 8191, 131071, 524287, 2147483647...
and perfect numbers :

6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128...

## Miscellaneous

There are other curiosities related with the sum of divisors :
• The "multiperfect numbers", equal to n times the sum of their divisors. Mention the number given by Frenicle in 1643 :
n = 236 × 38 × 55 × 77 × 11 × 132 × 19 × 312 × 43 × 61 × 83 × 223 × 331 × 379 × 601 × 757 × 1201 × 7019 × 112303 × 898423 × 616318177
Could you do as well as Frénicle and just check that the sum of aliquot parts of n is 5n ?

• We also know "amicable numbers" : The sum of proper divisors of each one is equal to the other
For instance 220 and 284.

• We name "aliquot sequence" the sequence of the sum of divisors of the preceding number, for instance, starting from 84 : 84, 140, 196, 203, 37, 1
Most of the time this sequence ends up with 1 (and stops as 1 has no proper divisor).
Sometimes this sequence seems to increase towards infinity : we don't know what happens with sequence starting from 276, we get numbers of more than 100 digits, whose sum of divisors are hard to compute !
In some cases, the sequence is periodic : returning to start point, for instance
12496, 14288, 15472, 14536, 14264, 12496 ...
This periodic sequences are named "sociable sequences".

## Inverse problem

That is to find a number N given the sum S of its divisors.
This is solved by searching divisors of S in the form ∑pi, with p prime.

For instance to search numbers whose sum of all divisors is 56 :
First of all get all divisors of 56 = 2³×7 : 1, 2, 4, 7, 8, 14, 28 and 56.
Next look for those of the form Q = 1+p+...pn.
To check if a number q is of the form Q, we look for prime factors p of q-1.
For each one, check if q(p-1)+1 is a power of p.

For instance to check if q=31 is a Q number : 31-1 = 30 = 2x3x5
p = 2 : 31×1+1 = 32 = 25 and 31 = 1+2+4+8+16
p = 3 : 31×2+1 = 63 not a power of 3
p = 5 : 31×4+1 = 125 = 53 and 31 = 1+5+25
Hence 31 is of the form Q in two ways.

The only divisors of 56 of the form Q = 1+p+...pn are :
4 = 1+3
7 = 1+2+4
8 = 1+7
14 = 1+13

Look for factorization of 56 with these divisors : 56 = 1×56 = 2×28 = 4×14 = 8×7 = 2×2×14 = 2×4×7 = 2×2×2×7.
Only factorizations 4×14 and 8×7 are made of Q numbers only.
4×14 = (1+3)(1+13) results into N = 3×13 = 39
8×7 = (1+7)(1+2+4) results into N = 7×4 = 28

All this doesn't work anymore if the sum of proper divisors is given instead of all divisors.

## Annexe 1 : Checking the Frenicle number

n = 236 × 38 × 55 × 77 × 11 × 132 × 19 × 312 × 43 × 61 × 83 × 223 × 331 × 379 × 601 × 757 × 1201 × 7019 × 112303 × 898423 × 616318177

Check first that all these numbers are primes (hard job with just paper and pencil ! The script giving the sum of divisors gives also the prime factorization)
The sum of all divisors of n is then :
S = (237-1) × (39-1)/2 × (56-1)/4 × (78-1)/6 × 12 × (133-1)/12 × 20 × (313-1)/30 × 44 × 62 × 84 × 224 × 332 × 380 × 602 × 758 × 1202 × 7020 × 112304 × 898424 × 616318178.
and we have to factorize all these numbers :

 237-1 = 223×616318177 (39-1)/2 = 9841 = 13×757 (56-1)/4 = 3906 = 2×32×7×31 (78-1)/6 = 960800 = 25×52×1201 12 = 22×3 (133-1)/12 = 183 = 3×61 20 = 22×5 (313-1)/30 = 993 = 3×331 44 = 22×11 62 = 2×31 84 = 22×3×7 224 = 25×7 332 = 22×83 380 = 22×5×19 602 = 2×7×43 758 = 2×379 1202 = 2×601 7020 = 22×33×5×13 112304 = 24×7019 898424 = 23×112303 616318178 = 2×73×898423
Grouping all prime factors :
S = 237 × 39 × 55 × 77 × 11 × 132 × 19 × 312 × 43 × 61 × 83 × 223 × 331 × 379 × 601 × 757 × 1201 × 7019 × 112303 × 898423 × 616318177 = 6n.
Sum of proper divisors is S - n = 5n QED.