Re: A Fun Recursive Prime Count Estimator
- From: Phil Carmody <thefatphil_demunged@xxxxxxxxxxx>
- Date: 20 May 2006 11:25:42 +0300
Keeping lots of context in as it's relevant:
quasi <quasi@xxxxxxxx> writes:
On 19 May 2006 18:34:42 -0700, gjedwards@xxxxxxxxx wrote:
An non-mathematician messes about with primes....and anticipates
flames...yes, yes, I know for this must just be a reworking (probably
not even that) of some other argument so please refer me to the
appropriate place - a cursory search hasn't helped, but as a
non-mathematician I'm not even sure what words to 'Google'....
Here's a recursive estimator for number of primes less than N. I like
it because it everything follows from a single definition: 2 is prime.
For some N (picked out of the number line by throwing a dart*), the
probability that it's divisible by 2 is 1/2 of course, by 3 its 1/3,
etc.
For any two primes the probabilities that a randomly select N is
divisible by them are independent, i.e. if N happens to be divisible by
2 then it doesn't influence your guess as to whether it might be
divisible by 3, 5, 7, etc. For example, take out all multiples of 2,
and still 1/3 of the remaining numbers are divisible by 3, etc.
If a number is *not* divisble by 2 (say) then the probabilty that it's
divisible by a multiple of 2 (4,6, etc) is zero. Likewise 3, etc.
Therefore, the probability that N is *not* divisible by any number up
to it's square root (i.e. it is prime) is:
(in plain text I don't know how you write that big pi-like symbol that
means 'multiply all terms between this indices' - the multiply version
of the Summation sign, so I'll use M to mean multiply terms for all n
between 2 and root(N)
p(N) = M ( 1- ( p(n) * 1/n ) )
In case I screwed this up here's the algorithm in C (returns
'probability' that N is prime):
double EstimatedPrimeProb(
double N
)
{
int i;
double prob = 1;
double rootN = sqrt(N);
if(N<=2)
return 1;
else
{
for(i=2; i<=rootN; i++)
{
prob = prob*( 1 - (EstimatedPrimeProb(i)/i ) );
}
return prob;
}
}
The key is that we only define the prime probability of a single number
(2) to be 1. For any other number, N, we know that to get a
probability we need to multiply out (1-1/p) for all primes up to its
root, but we're saying that we don't know what the primes actually are,
so we multiply out for all integers between 2 and root N, i.e. (1-1/n),
but modifying (1/n) by the probability that n is prime (which itself is
estimated by the same function according to p(n) ).
Adding up the probabilities up to N gives a great estimate (try the C
code) of the prime count and moreover the error doesn't seem to be
'biased'.
Flame away with how I've restated Theorem [insert here], but my simple
brain enjoyed the logic!
Your recursion works quite well.
My guess is you've recovered the essence of the counting method which
underlies the Prime Number Theorem. Even if that's the case, and I'm
not really sure, it was a very insightful discovery on your part.
Bravo.
Unfortunately it's probably wrong. The reason it's wrong is one
of the spookier things about the primes. The problem is that
the thing Gareth is trying to estimate (the product of (1-1/p)
terms) is itself wrong.
I once saw a wonderfully lucid description of the deviation,
but don't remember where. It may have been in Riesel or
Crandall & Pomerance. I really can't reproduce it here with
any reliability.
Basically, if you calculate the probability of a number
being prime using
a) the PNT
b) the combined probabilities of it not being divisible by
all primes<sqrt(p), assuming independence,
then your two values will be different, and related by a
constant factor. (Asymptotically.)
Primes are not independent. The fact that all of them
line up to divide 0 throws off modelling in terms of
probabilities.
See equation (14) at
http://mathworld.wolfram.com/Euler-MascheroniConstant.html
for a hint towards the connection.
It's possible that Gareth "mis-estimates" the thing that is
wrong in such a way that it once again gives a more correct
answer, I've not checked. It would be wonderful if it did,
and is far from impossible that such destructive interference
could take place.
Phil
--
The man who is always worrying about whether or not his soul would be
damned generally has a soul that isn't worth a damn.
-- Oliver Wendell Holmes, Sr. (1809-1894), American physician and writer
.
- References:
- A Fun Recursive Prime Count Estimator
- From: gjedwards
- Re: A Fun Recursive Prime Count Estimator
- From: quasi
- A Fun Recursive Prime Count Estimator
- Prev by Date: Re: " A way to solve Int{u=ln(x) to ln(x +2*Pi) , g(u)du } = tan(x) "
- Next by Date: Re: some problems
- Previous by thread: Re: A Fun Recursive Prime Count Estimator
- Next by thread: Re: MADONNA KIDNAPPED LOURDES! BRAD PITT MURDERED DRU SOJDIN!!!!
- Index(es):
Relevant Pages
|
