Problem

Given an integer $N$, find the Sum of Number of Divisors from $1 \to N$. That is, find $\sum_{i=1}^{N}NOD(i)$.

For example, find the Sum of Number of Divisors, $SNOD()$, when $N=5$. $SNOD(5)= NOD(1) + NOD(2) + NOD(3) + NOD(4) + NOD(5) = 1 + 2 + 2 + 3 + 2 = 10$.

Divisor Summatory Function

“In number theory, the divisor summatory function is a function that is a sum over the divisor function.” – Wiki

Divisor Summatory Function is defined as $D()$ in Wiki, but we will use $SNOD()$ in this article. Divisor Summatory Function finds Sum of Number of Divisors from $1 \to N$.

Brute Force Solution – $O(N^2)$ Approach

A simple solution is to run two nested loop which counts all divisors from $1 \to N$. It is simple but inefficient.

int SNOD( int n ) {
    int res = 0;
    for ( int i = 1; i <= n; i++ ) { // For each number from 1 - N
        for ( int j = 1; j <= i; j++ ) { // Find possible divisors of "i"
            if ( i % j == 0 ) res++;
        }
    }
    return res;
}

Using $NOD()$ - $O( N \times \frac{\sqrt{N}}{ln(\sqrt{N})})$ Approach

We can use the code for $NOD()$ to get the number of divisors for each integer from $1$ to $N$ instead of using a $O(N)$ loop. This will make it faster than the above solution.

int SNOD( int n ) {
    int res = 0;
    for ( int i = 1; i <= n; i++ ) {
        res += NOD(i);
    }
    return res;
}

Since $NOD()$ has same complexity as factorize(), the complexity for this code is $O( N \times \frac{\sqrt{N}}{ln(\sqrt{N})} )$.

Using Divisor List - $O(N)$ Approach

Suppose we are trying to find $SNOD(10)$. Let us write down the divisors for each integer between $1$ and $10$.

$NOD(1) = 1, : {1}$
$NOD(2) = 2, : {1 , 2}$
$NOD(3) = 2, : {1 , 3}$
$NOD(4) = 3, : {1, 2, 4}$
$NOD(5) = 2, : {1, 5}$
$NOD(6) = 4, : {1, 2, 3, 6}$
$NOD(7) = 2, : {1, 7}$
$NOD(8) = 4, : {1, 2, 4, 8}$
$NOD(9) = 3, : {1, 3, 9}$
$NOD(10) = 4, : {1, 2, 5, 10}$

So $SNOD(10) = 1 + 2 + 2 + 3 + 2 + 4 + 2 + 4 + 3 + 4 = 27$.

Now, look at the divisor list for each of integer between $1$ and $N$. Each divisor in the divisor lists contributes $1$ to the result. There are $27$ divisors in total.

How many times do we find $1$ in the divisor lists? It will appear once for every integer it can divide from $1$ to $N$. $1$ can divide $\frac{N}{1}$ numbers. So it appears $\frac{10}{1} = 10$ times.

Repeat for $2 \to N$. How many times do we find $2$? $2$ can divide $\frac{10}{2} = 5$ numbers, namely ${2,4,6,8,10}$. So it will appear $5$ times.

By repeating this from $1$ to $N$ we can find $SNOD(N)$.

int SNOD( int n ) {
    int res = 0;
    for ( int i = 1; i <= n; i++ ) {
        res += n / i;
    }
    return res;
}

We removed $NOD()$ from the code in line $4$ and replaced it with $\frac{n}{i}$.

Using Divisor Pairs - $O(\sqrt{N})$ Approach

Let us create another list. Instead of making divisor list, we will make "Ordered Divisor Pair" list for each value between $1$ to $N$. A divisor pair of value $X$ is a pair $(A, B)$ such that $A \times B = X$. Ordered pair means if $A \neq B$, then $(A, B)$ is a different pair than $(B, A)$.

$NOD(1) = 1, : (1,1)$
$NOD(2) = 2, : (1,2) (2,1)$
$NOD(3) = 2, : (1,3)(3,1)$
$NOD(4) = 3, : (1,4)(2,2)(4,1)$
$NOD(5) = 2, : (1,5)(5,1)$
$NOD(6) = 4, : (1,6)(2,3)(3,2)(6,1)$
$NOD(7) = 2, : (1,7)(7,1)$
$NOD(8) = 4, : (1,8)(2,4)(4,2)(8,1)$
$NOD(9) = 3, : (1,9)(3,3)(9,1)$
$NOD(10) = 4, : (1,10)(2,5)(5,2)(10,1)$

The "Ordered Divisor Pair" list is almost same as "Divisor List". The only difference is that each divisor $A$ is now paired with $B = \frac{X}{A}$.

Now, $NOD(X)$ represents number of ordered divisor pairs $(A,B)$ such that $A \times B = X$. So, $SNOD(N)$ is same as number of ordered divisor pairs such that $A \times B \leq N$.

How to find Number of Ordered Divisor Pairs $\leq N$?

We can find this by following three steps.

1. Find number of divisor pairs $(A, B)$ where $A < B$

What are the possible values for $A$? Can it ever be $> \sqrt{N}$? No. If $A > \sqrt{N}$, then with $B>A$, $B$ will be $> \sqrt{N}$ and $A \times B$ will be $ > N$. So $A$ can only be between $1$ and $\lfloor \sqrt{N} \rfloor$.

Let $u = \lfloor \sqrt{N} \rfloor$. Then for each value of $A$ between $1$ and $u$, what are the possible values of $B$?

For any value of $A$, there are $\frac{N}{A}$ possible values of $B$ for which $A \times B$ does not exceed $N$. For $N=10$ and $A=2$, there are $\frac{10}{2}=5$ possible values for $B$, and they are ${1,2,3,4,5}$. Multiplying $A=2$ with any of these values produces value $\leq N$. But we need $B > A$. So we omit ${1,2}$ from the list. We can only use ${3,4,5}$ as $B$.

So, for any value of $A$, there will be $\lfloor \frac{N}{A} \rfloor$ possible values of $B$. The values will be from $1$ to $\lfloor \frac{N}{A} \rfloor$. Out of those, we have to omit values that are $\leq A$. So we can use $\lfloor \frac{N}{A} \rfloor - A$ values for $B$.

For example, $N=10$. Then $u=\lfloor \sqrt{10} \rfloor = 3$. When $A=1$, number of legal values we can use is $\lfloor \frac{10}{1} \rfloor - 1 = 9$. Namely, $B$ can be one of ${2,3,4,5,6,7,8,9,10}$.

When $A=2$, legal values are $\lfloor \frac{10}{2} \rfloor - 2 = 3$. $B$ can be ${3,4,5}$.
When $A=3$, legal values are $\lfloor \frac{10}{3} \rfloor - 3 = 0$.

$A$ cannot be bigger than $u$. So number of $(A, B)$ pairs such that $A \times B \leq 10$ and $A < B$ is 12.

2. Multiply the result with $2$

Once we find the number of pairs $(A, B)$ such that $A < B$ and $A \times B \leq N$, we multiply that number with $2$. That is because we want to find the number of ordered divisor pairs. When $A \neq B$, each pair $(A, B)$ will occur in "Ordered Divisor Pair" list as $(B, A)$ again.

Once we double the number, our result contains the number of ordered pair $(A, B)$ such that $A \neq B$ and $A \times B \leq N$.

3. Add the number of pairs $(A, B)$ where $A = B$

We still did not count pairs where $A = B$ and $A \times B \leq N$. How many pairs can there be? Since $A$ must be between $1$ and $u$, there cannot be more than $u$ such pairs. The pairs will be $(1,1),(2,2)...(u,u)$.

Code for $O(\sqrt{N})$ Approach

int SNOD( int n ) {
    int res = 0;
    int u = sqrt(n);
    for ( int i = 1; i <= u; i++ ) {
        res += ( n / i ) - i; //Step 1
    }
    res *= 2; //Step 2
    res += u; //Step 3
    return res;
}

Reference

1. forthright48 - Number of Divisors of an Integer - https://forthright48.com/2015/07/number-of-divisors-of-integer.html
2. Wiki - Divisor Summatory Function - https://en.wikipedia.org/wiki/Divisor_summatory_function

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

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

In number theory, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. – Wiki

The definition above is hard to understand. To put it simply, PNT provides us with an estimation for Prime-Counting Function.

What is Prime-Counting Function?

This brings out another Wiki definition:

In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number $x$. It is denoted by $pi (x)$ (this does not refer to the number $pi$). – Wiki

This definition is easy to understand. Prime-Counting Function, $\pi (N)$, gives us number of primes less than or equal to $N$. For example, $\pi (10) = 4$ since there are $4$ primes, ${ 2 , 3 , 5 , 7 }$, which are $\leq 10$.

PNT – Estimation for $\pi (N)$

So, as I was saying before, PNT provides us with an estimation for Prime-Counting Function. It states that:
$$ \pi(N) \approx \frac {N}{ln(N)}$$

The accuracy of the estimation increase as $N$ becomes larger.

Application

We can use the theorem for complexity analysis.

Reference

1. Wiki – Prime Number Theorem
2. Wiki – Prime-Counting Function