Subscription

Books
Shop
About

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?  

3 comments:

  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.

    ReplyDelete
  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 α

    ReplyDelete
  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 ;)

    ReplyDelete

Blog Archive

My Other Blogs

  • A Monkey man and a Giant Red Panda - Monkey Man review – Dev Patel’s directorial debut is a gory descent into darkness https://t.co/N6g823SEMI — Guardian US (@GuardianUS) March 12, 2024 t...
    4 days ago
  • try advertising - View this post on Instagram A post shared by ONLINE INTERIOR DESIGN STORE (@onlinealaba_interiors) Make sure you subscribe! Follow on facebook. Ord...
    5 days ago
  • art now, forever - View this post on Instagram A post shared by OkayAfrica. (@okayafrica) View this post on Instagram A post shared by Ayush Bhatt (@triyuginarayan_dham)...
    3 weeks ago
  • this moment, this place - wetin dey reign now: agba baller! and shallipopi. the baddest dog's name ever, by the way, Shall-E-Poppi Flavour N'Abania aka Flavour of Africa is fore...
    4 weeks ago
  • It's time... - but don't go away. Keep up with my other blogs. Read my books. Stay mathy. ✌
    1 year ago

About Me

Followers