What’s So Interesting About The Prime Counting Function?

1 mainMathematicians 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?

2 gaussIt 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.


One thought on “What’s So Interesting About The Prime Counting Function?

  1. Prateek, 15/7/17, 10:15 PM IST
    Good Macro Picture about the Prime Nos’ Counting Fn π(x) – spl in the Last Para under ‘Implications’.
    While on THIS Link on Primes { and also wrt yr other Link on Primes : https://prateekvjoshi.com/2015/09/30/the-underlying-pattern-of-prime-divisors/ : (even though I am yet to appreciate the (suddenly popped up) Formula for Distribution Function and Characteristic Function – in the article by Alex Beckwith ! ; Statistics Formulae are often difficult to arrive at / comprehend ?) } :
    I would like to have some doubts clarified (/ or atleast discussed upon) wrt this recent Discovery by Zhang :
    https://www.wired.com/2013/11/prime/ : Good Overview !
    Sudden Progress on Prime Number Problem Has Mathematicians Buzzing
    By Erica Klarreich, Quanta Magazine, dt 22nd Nov, 2013.
    For eg, the article states at one place :
    “- – – Zhang showed how to make an Admissible Comb with at least 3,500,000 remaining teeth by starting with a 70-million-tooth Comb and snapping off all but its Prime Teeth. – – -”
    I have prepared a whole Questionnaire on this Sieve / Comb etc – – –
    I would like to post those queries in some of yr blogs since there are quite a no of readers of yr blog.
    Sundar Krishnan

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s