# Sum of Divisors of an Integer

# Problem

Given an integer N, find the sum of all its divisors.

For example, find Sum Of Divisors (SOD) of $12$. $12$ has the following divisors, ${1, 2, 3, 4, 6, 12}$. So $SOD (12 ) = 1 + 2 + 3 + 4 + 6 + 12 = 28$.

# Sum of Divisor Function: $SOD(N)$ or $\sigma_{1}(N)$

The Sum of Divisors of $N$ is also called $\sigma_{1}(N)$. That’s just a fancy way of saying Sum of Divisors of $N$. You can read more on it from Wiki. I will refer to Sum of Divisors of $N$ as either $\sigma_{1}(N)$ or $SOD(N)$. They both mean same.

# Inefficient Solutions

Let us first look into some simple, but inefficient, solutions. These solutions are similar to the naive solutions we came up for “Number of Divisors of an Integer“.

## Loop Till $N$

This is the simplest solution. We loop from $1 \to N$ and add all numbers that divide $N$.

## Loop Till $\sqrt{N}$

If $N = A \times B$, where $A \leq B$, $A$ must be $\leq \sqrt{N}$. Using this fact we can run a loop from $1 \to \sqrt{N}$ and add all numbers that divide $N$ and their complements to result.

int SOD ( int n ) { int sqrtn = sqrt ( n ); int res = 0; for ( int i = 1; i < sqrtn; i++ ) { if ( n % i == 0 ) { res += i; //"i" is a divisor res += n / i; //"n/i" is also a divisor } } if ( n % sqrtn == 0 ) { if ( sqrtn * sqrtn == n ) res += sqrtn; //Perfect Square. else { res += sqrtn; //Two different divisor res += n / sqrtn; } } return res; }

At line $10$, we handle $sqrtn$ separately cause when $N$ is a perfect square we don't get different values for ${A, B}$ pair. For example, for $49$ we have a divisor pair $7times 7$. We need to add $7$ only once in our result.

# Using Prime Factorization

It is possible to find $SOD(N)$ using the prime factorization of $N$. Let us see an example for it.

$Let \ N = 12,$

$SOD(12)= 1 + 2 + 3 + 4 + 6 + 12,$

$SOD(12) = (2^0 \times 3^0) + (2 ^1 \times 3^0) + (2^0 \times 3^1) + (2^2 \times 3^0) + (2^1 \times 3^1) + (2^2 \times 3^1),$

$SOD(12) = 2^0 ( 3^0 + 3^1 ) + 2^1 ( 3^0 + 3^1 ) + 2^2 ( 3^0 + 3^1 ),$

$SOD(12) = ( 2^0 + 2^1 + 2^2 ) \times ( 3^0 + 3^1)$

This pattern emerges with any value of N. More generally, if $N= p_1^{a_1} \times p_2^{a_2} \times ... p_k^{a_k}$, then $$ SOD(N) = (p_1^0 + p_1^1 + p_1^2 ... p_1^{a_1} ) \times (p_2^0 + p_2^1 + p_2^2 ... p_2^{a_2} ) \times ... (p_k^0 + p_k^1 + p_k^2 ... p_k^{a_k} ) $$Using this formula and our code for Prime Factorization, we can write the function $SOD(N)$. This code is similar to $factorize()$. We only need to modify it in few places.

int SOD( int n ) { int res = 1; int sqrtn = sqrt ( n ); for ( int i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) { if ( n % prime[i] == 0 ) { int tempSum = 1; // Contains value of (p^0+p^1+...p^a) int p = 1; while ( n % prime[i] == 0 ) { n /= prime[i]; p *= prime[i]; tempSum += p; } sqrtn = sqrt ( n ); res *= tempSum; } } if ( n != 1 ) { res *= ( n + 1 ); // Need to multiply (p^0+p^1) } return res; }

For each prime we find in factorization, we need to find the corresponding value of $(p^0+p^1+...p^a)$. For that, we use `tempSum`

in line $6$. It contains $p^0$ initially. Then for each successful division at line $8$, we increase the power of $p$ in line $10$ and add it to `tempSum`

in line $11$. Eventually, we multiply the final sum to result at line $14$.

In line $17$, we check if we are left with a sole prime remainder. In this case, we know that $n$ is a prime so we simply multiply $p^0 + p^1 = 1 + n$ to the result.

# Reference

- Wiki - Divisor Function - https://en.wikipedia.org/wiki/Divisor_function
- forthright48 - Number of Divisors of an Integer - https://forthright48.com/2015/07/number-of-divisors-of-integer.html
- forthright48 - Prime Factorization - https://forthright48.com/2015/07/prime-factorization-of-integer.html