Prime Number Theorem

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

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.

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

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