Mathematicians have obsessed over prime numbers for centuries, and will continue to do so for the foreseeable future. Prime numbers are so enigmatic and fascinating that mathematicians just can’t stop thinking about them! Prime counting function is probably one of the most famous problems in this domain. This function simply counts the number of prime numbers less than or equal to a given number. Pretty straightforward! But why is this of such great importance? What are we going to do with this information?
Why do we care about this?
As you know, prime numbers are seemingly sporadic on the number line. So anytime mathematicians get a chance to generalize anything about prime numbers, they pounce on it. Let’s say you want to count of number of even numbers less than or equal to a given number. This is pretty easy, right? Just divide the number by 2 and take the floor value of the result. For example, if we consider 9, the number of even numbers less than or equal to 9 is 4. But as it turns out, we don’t have an exact formula to calculate the number of primes less than or equal to a given number. If we did, then the whole world of cryptography will turn on its head. Any information about the distribution of prime numbers would have serious implications in the world of cryptography, internet security, banking, and many more fields where we use encryption.
Is there an approximate formula for this?
It started all the way back in the second half of 18th century when the legendary mathematician, Carl Friedrich Gauss, came up with an estimate. The prime counting function is denoted by π(x). He said that the number of primes less than or equal to a given number is approximately x/ln(x), where ln(x) is the natural logarithm. Even though this puts an estimate on π(x), it starts drifting as we move along the number line. So mathematicians starting thinking about putting a tighter bound on this function. In order to come up with a precise function, they went from logarithmic integrals to sieve of Eratosthenes to combinatorics. They have now finally settled on Reimann Zeta function that puts a much tighter bound on pi(x). The formulation is too mathematical to be discussed in this blog post, but you can read more about it online.
What are the implications here?
There are few nice implications of this whole prime counting fiesta! The prime counting function led to the formulation of the Prime Number Theorem, one of the most important results in number theory. We can now say that the nth prime number is approximately n*ln(n). This is actually a rough estimate. A more precise estimate is n*(ln(n) + ln(ln(n)) – 1). But basically, we are now able to come up with a rough estimate about the location of the nth prime number. Before this, it would have been a random guess! Another implication is that any given number, x, has a chance of 1/ln(x) of being a prime number. This means that as we move along the number line, prime numbers become sparse. These points are actually very insightful and they give us an understanding about the underlying structure of the prime numbers.