Saturday, August 3, 2013

The difference between two (consecutive) prime numbers

Recall that
The Continuous derivative method of finding a formula for the estimated difference between two prime numbers
Applying the Product Rule for differentiating functions, P'(n) , the derivative of Prime(n),
is ~= α(n.1/n + 1.log n) = α( 1 + log n )
Yes, the derivative is usually for continuous functions, while Prime[n] is discrete, but approximating this way is OK because it's useful. 
What the derivative means is: let Δ be a reasonably small value, then P(n+Δ) ~= P(n) + Δ.P'(n)
This implies that if we want P(n+1), we may put Δ=1 above and the (n+1)th prime number is approximately P(n) + P'(n), i.e. just add α( 1 + log n )  to the nth prime number.
Got it?
The (n+1)th prime number, note α around 1.1
What is this useful for? 
We've already seen that we may estimate the prime numbers with so-so results using the formula for the nth prime.
But we may sometimes get closer approximations when we seek a prime number, the (n+1)th prime for instance, using the difference formula and prior knowledge of the nth prime.   

If we know the 99th prime number to be 523, what is the 100th prime?
Add 1.2(1+log99) to 523 , to get 523+6.714 ~= 530.
Oh well, this is not a prime number and it's still pretty far from the 100th prime (541), but the formula works better sometimes,
e.g. the 101st prime, given the 100th prime is 541 is
estimated to be 541+1.2(1+ln100) = 541 + 6.726 ~= 547.7
and in actual fact is 547

The finite/discrete derivation of the formula for the estimated difference between two consecutive primes
This yields similar/close results to the continuous derivative steps above:
P[n+1] - P[n] ~= α.(n+1).log(n+1) - α.n.logn
 = α [ n.log(n+1) + log(n+1) - n.log(n) ] 
 = α [ log ( (n+1)^n ) - log (n^n) + log (n+1) ] 
=  α [ log ( {(n+1) / n}^n . (n+1) ) ]
= α [ log {(1 + 1/n)^n .(n+1)} ] 
and at this point, you need the fact that (1+ 1/n)^n is approximately e, which has log 1, for reasonably large n.  For example (1+1/5)^5 is about 2.5, while 1.01^100 is about 2.7.  Anyway, moving on...
so P[n+1] - P[n] ~= α.log(e.(n+1)) = α.[1+log(n+1)] 

What should be done about the difference between the continuous and the discrete formulae?
Ignore the fact that the difference has 1+log(n+1) here, but 1+log(n) in the first derivation.
We might have even chosen to use the derivative at n+1/2Δ instead of at n as we did, and got the difference P[n+1] - P[n] ~= α.[1+log(n+ 1/2)]   
Anyway, when n>>1, log(n) is very close to log(n+1) in the sense that it's much smaller than 1 and much smaller than n: how to see this is another short exercise in using the derivative :) i.e. the derivative of log(n) is 1/n which is << 1 << n

Answers to two previous questions
 1. How does one know that there is no largest PRIME number?  Because when we think we've found the biggest, here is an estimate for the next one...add 1+log(n+1) to it. 
2. How do you know if α > 1?  Sorry I thought I knew, but I don't (yet.) 

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?  

My Other Blogs

About Me