For me, the story of finding it did not start with that specific question, it started with play.
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
In summary,
 |
| Clearly useful for estimating the nth prime number |
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?
There is a thing called The Prime Number Theorem. It predates Mathematica and even electronic computers, so it relies on harder proofs hehehe.
ReplyDeleteFrom 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.
Details on my previous comment:
ReplyDeleteIf 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 α
To follow up on the last comment:
ReplyDelete"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 ;)