Re: Methods that count primes without counting primes or referringto them...
From: mechmech (bbb_at_ccc.com)
Date: 10/12/04
- Next message: Dave Seaman: "Re: Fundamental Theorem of Calculus"
- Previous message: J.E.: "Re: Skolem's Paradox and why is math the way it is?"
- In reply to: Bob Silverman: "Re: Methods that count primes without counting primes or referringto them..."
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 12 Oct 2004 18:47:06 -0400
here's a method that does not use a lot of enumeration. It is based on the
simple fact that instead of finding the primes and counting them, we find
the composites and eliminate them from the list. At the end you end up with
a bunch of primes that can be easily counted.
counting the primes is easy:
take the arithmetic progression s1=(6k-1) and s2=(6k+1), they have all the
primes except the first two ( 2 and 3). Given s1 and s2 how can you tell
which member is a prime and which one is a composite? simple!
1-case of s1=(6k-1)
take the matrix m3(i,j)=6ij+i-j with i=j=1,2,3,4,5,6.... to get
m3(i,j)=6,11,13,16,20,21....
the values of m3(i,j) give the positions of the composite numbers whithin s1
meaning m3(1,1)=6 tells you that the 6th element of s1 is a composite
etc.......
2-case of s2=(6k+1)
in this case we need two matrices to produce the indices of the composite
numbers within s2
m2(i,j)=6ij+(i+j) and m1(i,j)=6ij-(i+j). it will give you the indices of
all the composite
numbers within s2. for example m2(1,1)=8 tells you that the 8th element of
s2 is a composite. m1(1,1)=4 tells you that the 4th element of s2 is a
composite. when you have produced your matrix elements, you have by the same
token the
positions of the composite and therefore that of the primes.
of course, there is really no need to store the matrix elements of m1, m2
and m3. When you take a number N, we know that 4/6 N are composites and we
don't waste time checking that. We only need to check 1/6N for the series S1
and 1/6N for S2 or N/3.
just a thought............
"Bob Silverman" <anonymous@mathforum.org> wrote in message
news:200410121628.i9CGSX113531@proapp.mathforum.org...
> On 12 Oct 2004, robert j. kolker wrote:
> >
> >
> >David Kastrup wrote:
> >>
> >> Sure. Inclusion/Exclusion counting. Legendre's algorithm does that.
> >
> >That still involves a lot of ennumeration, if I follow you. Inclusion
> >exclusion will eliminate all composite numbers, and clearly the rest are
> >prime, but much ennumeration is being done. Is there a more direct way?
>
> Your question really has no mathematical meaning. What do
> you mean when you say "direct" way? Please define your terminology.
> I may be very wrong but it seems as if you are asking "how do
> I compute pi(n) without doing any computing".
>
> How would you, under your purported definition, compute (say)
> sin(pi/37) to 25 digits? What would be a "direct" way?
>
> Would an expression of pi(n) in terms of a contour integral satisfy
> your request for a "direct" way?
>
> Some functions require extensive computation to evaluate them.
> Although we have no lower bound on an algorithm to compute pi(n)
> it is unlikely (based on experience) that a polynomial time
> algorithm exists to compute it.
>
- Next message: Dave Seaman: "Re: Fundamental Theorem of Calculus"
- Previous message: J.E.: "Re: Skolem's Paradox and why is math the way it is?"
- In reply to: Bob Silverman: "Re: Methods that count primes without counting primes or referringto them..."
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
