## 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$.

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.

### 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 $7\times 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\times3^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; }

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 - http://forthright48.blogspot.com/2015/07/number-of-divisors-of-integer.html
- forthright48 - Prime Factorization - http://forthright48.blogspot.com/2015/07/prime-factorization-of-integer.html

## No comments:

## Post a Comment

Leave comments for Queries, Bugs and Hugs.