Upper Bound for Number Of Divisors

Given a number $N$, we can find its number of divisors using prime factorization. But when the number gets too big, it gets difficult to factorize, thus harder to find the number of divisors. So given a number $N$, can we estimate at most how many divisors N can have? That is, we want to find the upper bound for NOD.

NOD Upper Bounds

We proceed from loose to tighter bounds.

$NOD(N) \leq N$

A number which is greater than $N$ cannot divide $N$. For $N>2$, we can further say $NOD(N) < N$, but the improvement is negligible.

Can we make the limit tighter?

$NOD(N) \leq \frac{N}{2} + 1$

A divisor $D$, such that $\frac{N}{2} < D < N$  cannot divide $N$, since the result would be less than $2$ and greater than $1$, a fraction. So possible divisors are $D \leq \frac{N}{2}$ and $N$.

Better than before by half, but its possible to make it tighter.

$NOD(N) \leq 2 \times \sqrt{N}$

If we write $N = A \times B$, where $A \leq B$, then $A \leq \sqrt{N}$. Each of ${A,B}$ forms a divisor pair for $N$. $A$ can take any value from $1 \to \sqrt{N}$, so it is possible to form only $\sqrt{N}$ pairs of divisors. Thus, there can be at most $2 \times \sqrt{N}$ divisors for $N$.

$NOD(N) \approx 2 \times \sqrt[3]{N}$

I didn’t know about this approximation until I read a blog post on Codeforces. From there I found out that in practice we can safely use $\sqrt[3]{N}$ as an upper bound, though I failed to understand the proof. Apparently, this approximation has been tested for $N \leq 10^{18}$, which is large enough to be used in programming contests.

Using Highly Composite Numbers

Sometimes we need upper bound for small values of N. For example, in a problem you might need to find an upper bound of NOD for $N \leq 10^9$. For such small values of $N$ we could use NOD of largest Highly Composite Number (HCN), which is less than or equal to $N$, as an upper bound.

Read more about HCN here.

For programming contest, we could memorize values of HCN that comes frequently. Mainly $1344$ for $N \leq 10^9$ and $103,680$ for $N \leq 10^{18}$.

Application 

The upper bound for NOD is needed for complexity analysis.

Reference

  1. Codeforces – Upper bound for number of divisors: http://codeforces.com/blog/entry/14463
  2. forthright48 – Highly Composite Numbers: https://forthright48.com/2015/07/highly-composite-numbers.html

Highly Composite Numbers

Definition

A Highly Composite Number (HCN) is a positive integer which has more divisors than any smaller positive integer (Wiki), i.e, if $NOD(N) > NOD(i)$, where $ 0 < i < N $, then $N$ is HCN.

For example, $6$ is HCN cause $NOD(6)=4$ which is bigger than $NOD{1,2,3,4,5} = {1,2,2,3,2}$.

Here are the first few HCN: $1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240$ – A002182

Properties of Highly Composite Numbers

There are two properties of HCN and both of them are related to prime factorization.

Suppose we have a HCN with prime factorization $HCN=p_1^{a_1} \times p_2^{a_2} … \times p_k^{a_k}$, then:

  1. First K Primes: The prime factorization of HCN will contain the first K consecutive primes. If it doesn’t, then we can replace the $k^{th}$ prime in factorization with a smaller prime and still have the same NOD. For example, $2^2 \times 5 = 20$ cannot be an HCN, since we can replace prime factor $5$ with $3$ and get $2^2 \times 3=12$ which is smaller than $20$ and has the same NOD.

  2. Non-Increasing Power of Primes: Power of prime factors of HCN, i.e, ${a_1, a_2 … a_k}$ will form a non-increasing sequence. Why is that? If power $a_j > a_i$, where $i < j$, then we can simply swap them to get a smaller number with the same NOD. For example, $2 \times 3^2= 18$ cannot be HCN cause we can swap power of prime $2$ and $3$ to get $2^2 \times 3 = 12$ which is smaller with same NOD.

Therefore we conclude that Highly Composite Numbers are product of Primorials (Primorials are same as Factorials, but instead of natural number we multiply primes. $p_3 = 2 \times 3 \times 5$ and $p_5 = 2 \times 3 \times 5 \times 7 \times 11$ )

For example, $180$ is HCN and it can be decomposed into $180 = p_3 \times p_2 = (2 \times 3 \times 5) \times ( 2 \times 3 )$.

Generating Highly Composite Numbers

Problem: Given an integer N, find the largest HCN which is smaller than or equal to N.

This problem can be solved using backtrack. We just need to ensure that we satisfy the two properties of HCN.

Let’s try to solve it for when $N=10^9$. We know that $p_{10} = 6469693230$, so we will only have primes ${ 2 , 3 , 5 , 7 , 11 ,13 , 17 , 19 , 23 }$ in HCN factorization.

Now, we will assign power to each of the primes in non-increasing order to generate numbers and corresponding NOD. Out of all the numbers generated, we will keep the one with the highest NOD and in case of a tie, the one with smallest value.

// prime[] is a list of prime.
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23 };

int resNum, resDiv, n;
void recur ( int pos, int limit, long long num, int div ) {
    if ( div > resDiv ) { // Get the number with highest NOD
        resNum = num;
        resDiv = div;
    }
    else if ( div == resDiv && num < resNum ) { //In case of tie, take smaller number
        resNum = num;
    }

    if ( pos == 9 ) return; //End of prime list

    long long p = prime[pos];

    for ( int i = 1; i <= limit; i++ ) {
        if ( num * p > n ) break;
        recur ( pos + 1, i, num * p, div * ( i + 1 ) );
        p *= prime[pos];
    }
}

Line $2$ contains a prime list. It contains first $9$ primes so it will work correctly for $N\leq 10^9$. Line $4$ contains global variables to store the result. resNum to hold required value and resDiv to hold its NOD. Line $19$ checks if multiplying $prime[pos] ^ i$ with res is becoming bigger than $N$ or not.

In line $20$, we call $recur()$ with $pos+1$ as we want to work with the next prime in the list, $i$ as the new limit since we don’t want the next prime to have a power greater than the current one. The next two parameters are adjusted accordingly to maintain value and NOD.

In order to solve the above problem for $N=10^9$, we have to initiate and call $recur()$ from $main()$ in following manner.

int main () {
    n = 1000000000;
    resNum = 0;
    resDiv = 0;
    recur ( 0, 30, 1, 1 );
    printf ( "%d %d\n", resNum, resDiv );
}

In line $5$, we call recur(0,40,1,1). pos is assigned $0$ since we want to start with the first prime in prime list. limit parameter is set to $30$ since $2^{30} > N$.

Reference

  1. Wiki – Highly Composite Numbers: https://en.wikipedia.org/wiki/Highly_composite_number
  2. Primorials: https://en.wikipedia.org/wiki/Primorial

Number of Divisors of an Integer

Problem

Given an integer $N$, find its number of divisors.

For example, $12$ has the following divisors $1,2,3,4,6$ and $12$. So its number of divisors is $6$.

Number Of Divisors Function: $NOD(N)$ or $\sigma_{0}(N)$

Number of Divisors of N is also called $\sigma_{0}(N)$. That’s just a fancy way of asking for the number of divisors of N. You can read more on it from Wiki. I will refer to Number of Divisors of $N$ as either $\sigma_0(N)$ or $NOD(N)$. They both mean same.

Brute Force Method O(N)

Anyways, what is the easiest way to find Number of Divisors (NOD)? We can try to divide $N$ with all numbers from $1-N$ and keep count of how many of those numbers divide $N$. This will definitely work, but obviously we need to do better.

Optimized to O($\sqrt{N}$)

In “Primality Test – Naive Methods, we established that if we can write $N=A \times B$, then one of ${A,B}$ must be $<=\sqrt{N}$.

So using that same idea we can find NOD by simply looping till $\sqrt{N}$ and check if that particular number divides $N$. If it doesn’t then it is not a divisor and if it does then we found a ${A,B}$ pair of divisors. If $A \neq B$, then we add $2$ to result, otherwise we add $1$.

Examples

Suppose $N=24$. We need to loop till $\lfloor {\sqrt{24}} \rfloor= 4$. We get the following pairs of divisors, ${1,24}, {2,12}, {3,8}, {4,6}$. So our answer is $8$.

Let’s try again with $N=36$. We need to loop till $\lfloor {\sqrt{36}} \rfloor= 6$. We get the following pairs of divisors, ${1,36}, {2,18}, {3,12}, {4,9}, {6,6}$. So our answer is $9$. Notice that the last pair does not satisfy the condition $A \neq B$. So we add one for that pair.

This brings out an interesting observation. NOD of $N$ is always even except for when $N$ is a perfect square.Because whenever $N$ is perfect square, $\sqrt{N}$ would be its divisor and it will form a pair with itself.

Code Using Loop till $\sqrt{N}$

int NOD ( int n ) {
    int res = 0;
    int sqrtn = sqrt ( n );
    
    for ( int i = 1; i < sqrtn; i++ ) {
        if ( n % i == 0 ) res += 2; // Found a divisor pair {A,B}
    }
    
    // Need to check if sqrtn divides n
    if ( n % sqrtn == 0 ) {
        if ( sqrtn  sqrtn == n ) res++; // If n is perfect square
        else res += 2; // Not perfect square
    }

    return res;
}

We loop from $1$ to $\sqrt{N}-1$ at line 5. Then at line 10, we handle $\sqrt{N}$ seperately.

Using Prime Factorization

It is possible to find NOD from prime factorization of N. Suppose $N=12$. Its prime factorization is $2^2 \times 3$. Is it possible to divide $12$ with $5$? No. Cause the prime factorization of $12$ does not contain $5$. We can divide $N$ with primes that appear in factorization of $N$.

Next, can we divide $12$ with $2^3$? No. The power of $2$ in prime factorization of $12$ is $2^2$. So we cannot divide $12$ with $2^3$, since $2^2$ is not divisible by $2^3$.

So, if we are trying to divide $N$, that has prime factorization $N=p_1^{a_1} \times p_2^{a_2} \times ...p_x^{a_x} $, then the divisors of $N$, $D$, will have prime factorization of form $D=p_1^{b_1} \times p_2^{b_2} \times ...p_x^{b_x}$, where $b_i <= a_i$.

For example, divisor of $12=2^2 \times 3$ will have prime factorization, $D=2^x \times 3^y$, where $x <= 2, y <= 1$. When $x = 1$ and $y=1$, $D=2^1 \times 3^1=6$ which is a divisor of $12$. If we use a different combination of $[x,y]$, then we get a different divisor. So how many different combination can we use here? We know that, $0<=x<=2$ and $0<=y<=1$. So for $x$ we can use ${0,1,2}$ and for y we can use ${0,1}$. So we can use $3 \times 2=6$ combinations of ${x,y}$. And that is our NOD.

So, if $N=p_1^{a_1} \times p_2^{a_2} \times ...p_x^{a_x}$, then $D=p_1^{b_1} \times p_2^{b_2} \times ...p_x^{b_x}$. We get new divisors for using different combination for ${b_1,b_2...b_x}$. How many different combinations can we make? $(a_1+1) \times (a_2+1) \times...(a_x+1)$. Therefore, $\sigma_0(N) = (a_1+1) \times (a_2+1) \times...(a_x+1)$.

So basically, in order to find NOD, all we need to do is factorize $N$, then take each of its prime factors power, increase them by $1$ and finally multiply all of them. Easy right?

Examples

$N=12=2^2 \times 3$. $NOD(N)= (2+1) \times (1+1) = 6$
$N=15=3 \times 5$. $NOD(N)= (1+1) \times (1+1) = 4$.
$N=252 = 2^2 \times 3^2 \times 7$.
$NOD(N)=(2+1) \times (2+1) \times (1+1) = 18$.

Try out this yourself using other small values of N.

Code Using Prime Factorization

The code for $NOD$ is not very different from the one we used for factorize() in Prime Factorization of an Integer. We just need to modify it slightly to suit our needs.

int NOD ( int n ) {
    int sqrtn = sqrt ( n );
    int res = 1;
    for ( int i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) {
        if ( n % prime[i] == 0 ) {
            int p = 0; // Counter for power of prime
            while ( n % prime[i] == 0 ) {
                n /= prime[i];
                p++;
            }
            sqrtn = sqrt ( n );
            p++; // Increase it by one at end
            res *= p; // Multiply with answer
        }
    }
    if ( n != 1 ) {
        res *= 2; // Remaining prime has power p^1. So multiply with 2/
    }
    return res;
}

I have highlighted the lines that are different from factorize().

Reference

  1. Divisor Function