Thursday, August 1, 2013

The nth prime number

What is the relationship between Prime[n] and n?  Prime[n] by the way is a "function" in Mathematica that gives the nth prime number.
For me, the story of finding it did not start with that specific question, it started with play.
I was playing with the tutorial on my Mathematica installation (v7), it had a plot of Prime[n] against n, say for n from 1 to 100.  So of course you extend that say 1 to 10000, wow cool, and extend it again till the program stalls.
The next time you try this, you notice the graph of Prime[n] against n which is many points really close together bears a striking resemblance to...log(n) or something.  So you plot Prime[n] against n.log(n) and sure enough, well it's a little stochastic looking but it sort of stays within a small constant range 1.1 - 1.2.  More precisely, for small n, Prime[n] ~= 1.2 n log(n)...and for the largest n I could compute, Prime[n] ~= 1.1 n log(n), or if you let α vary a little around 1.15, Prime[n] = α . n log (n)

Why won't I just show you the plots?  Well, I've been procrastinating forever writing this post, and just minutes ago found that my Mathematica license expired.  Dang!  I thought the license was forever to be honest :) Fingers crossed it'll be renewed soon.

Cool question: I wonder if there is a limit to what α can be.  It seems to decrease gently from 1.2 for n in the 10-1000 range, to 1.1 for n much larger.  But for n a lot larger than that, is α ever going to go below 1?  Is there a guarantee that the "slope" of the graph Prime[n] against n.log(n) , averagely speaking, stays above 1 even for n very large?  I'll say yes for now, that the asymptote of that slope or ratio is 1 and I have "proof", but I want to know what you think.

In summary,
Clearly useful for estimating the nth prime number
Note: The log used in this law is the natural logarithm (so called ln) not the base 10 logarithm (often denoted log)

Meanwhile, we can use the knowledge we already have, say to compute the 100th prime number as Prime[100] ~= 1.2 * 100 ln 100
~= 1.2 * 100 * 4.60517018599 
= 552.620422319 , so the 100th prime number is around 552 or 553?  
If we instead used α = 1.1 we would get the estimate Prime[100]=506.568720459
Nifty tool: I just typed "what is log 100" in google search box, and a calculator appeared.  Just remember to use ln not log.  
In reality, the 100th prime number is 541, not 553, not 507, but still, not too bad?  


  1. There is a thing called The Prime Number Theorem. It predates Mathematica and even electronic computers, so it relies on harder proofs hehehe.

    From Wikipedia, "Informally speaking, the prime number theorem states that if a random integer is selected in the range of zero to some large integer N, the probability that the selected integer is prime is about 1 / ln(N), where ln(N) is the natural logarithm of N. "

    This statement is related to my approximation of the nth prime, since it can be restated as:
    from 0 to N, there are about N/ln(N) prime numbers.
    Or perhaps that the N/ln(N)-th prime is approximately N.
    Or the Mth prime is approximately M.ln(M), which is roughly what I've proposed, with some mild modification from constant terms.

  2. Details on my previous comment:
    If the N/ln(N)-th prime is approximately N,
    does that imply that the Mth prime is approximately M.ln(M) ?

    Not really. Actually, the ??th prime is about M.ln(M),
    where ?? is MlnM / (ln(MlnM)) , right?
    So, not the Mth prime but the [MlnM / (lnM + lnlnM)]-th prime is MlnM.
    We can use the approximation 1/(1+a) ~= 1-a since a, in this case the ratio (lnlnM)/(lnM), is small. So the [M(1 - lnlnM/lnM)]-th prime is MlnM.

    For us to say the Mth prime is MlnM requires M to be so large that lnlnM/lnM is about 0 and can be ignored. But for the range of M we have looked at, what is that ratio, also called a?
    When M is about 100 that is 10^2 about e^4.6 ,
    then a = lnlnM/lnM = ln4.6 / 4.6 ~= 1.5 / 4.6 ~= 0.3
    For M about a thousand, the a ratio is about 0.3
    For M around a million, a is about 0.2
    For M = e^30 (around 10 trillion) , a is ln30 / 30 ~= 0.1

    Observe closely, and we see how including α performs this compensation.
    The ((1-a)M)th prime is MlnM
    By further approximation, the Mth prime is about (1+a)MlnM (Comments on making this approximation, please?) with (1+a) being the correcting term α

  3. To follow up on the last comment:
    "Observe closely, and we see how including α performs this compensation.
    The ((1-a)M)th prime is MlnM **
    By further approximation, the Mth prime is about (1+a)MlnM with (1+a) being the correcting term α "
    Here are the steps in making this further approximation.
    Set K = (1-a)M
    then ** means the
    Kth prime is K/(1-a) ln K/(1-a) which is
    roughly K(1+a)[lnK-ln(1-a)]
    or (1+a)KlnK since ln(1-a) ~= 0
    You could do these steps more carefully e.g. using 1/(1-a) = 1+a+a^2+a^3+... and -ln(1-a)= a +(1/2)a^2 + (1/3)a^3 + ... (Maclaurin series)
    Much ado...the bottom-line is that the formulae are alike: if the N/logN th prime is N, we can show that the Kth prime is αKlnK

    Similarly, from the statement that the Nth prime is αNlnN, we can substitute N/lnN for N, so that
    the N/lnN th prime is α(N/lnN)ln(N/lnN)
    = αN.[(lnN-lnlnN)/lnN]
    = αN(1-a) = N (1+a)(1-a) = N(1-a^2)
    ~= N

    Alright now you believe me ;)


My Other Blogs

  • #Glocal #business #news bits - With these types of forums (Breakfast chats with seasoned founders and CEOs), we can share our experiences and fast track our growth - Deji Akinyanju (Fo...
    11 hours ago
  • Prizes - Top of the top: 10 Nobel Laureates Who Changed The World See all the Nobel Prizes. Advertisement: Read my books. - [image: Nobel Prizes in Physics,...
    2 days ago
  • Who Will You Marry? Answer in the comments :) - Really good quiz here, you answer 10 questions and it reveals 'who is the right person for you' :) I want to know what result you got, so comment. And ...
    5 days ago
  • o O ~ circles ~ O o - Want REALbubbler Membership? Want fine African Literature? (Preview) Nigerian Lifestyle A-Z at
    2 weeks ago
  • Paradise Road - It was a morning like any other morning, on a road like any other road. 8 a.m. “Conductor, give me my change.” The dust, smoke, and everything were ma...
    4 weeks ago

About Me