Re: Computational complexity, number theory tidbits

From: James Harris (jstevh_at_msn.com)
Date: 08/03/04 

Date: 3 Aug 2004 16:59:10 -0700

jstevh@msn.com (James Harris) wrote in message news:<3c65f87.0408030659.57840baf@posting.google.com>...
> No Way <Not@real.com> wrote in message news:<cbkug0ho0dbvvqbmbu55tmiutl3pq7a5cn@4ax.com>...
> > On 2 Aug 2004 17:36:25 -0700, jstevh@msn.com (James Harris) wrote:
> >
> > >Neat. It looks like there's a pattern.
> >
> > Yes, it's constantly combing two terms with:
> >
> > [(N+k)/(2*k)] = [N/k] - [N/(2*k)]
>
> How do you get that?
>
> >
> > >It looks like inclusion-exclusion with an easy to determine offset.
> > >
> > >Can you prove that the pattern holds across all odd primes?
> > >
> > >Given that Legendre's Method, which also uses inclusion-exclusion, is
> > >far less efficient, can those terms be compressed in some way along
> > >the lines of what has been used with Legendre's?
> >
> > Legendre's method (from the internet, so it might not be correct):
>
> Legendre's Method also called Legendre's Formula gets a count of prime
> numbers using the inclusion-exclusion method that's been discussed.
>
> Like to count the primes up to 10, you'd have
>
> 10 - [10/2] - [10/3] + [10/6] + 2 = 4

OOPS! Knew the answer ahead of time, so I cheated and screwed up.

That should be

10 - [10/2] - [10/3] + [10/6] + 2 - 1 = 4

> and those primes, of course, are 2, 3, 5 and 7.
>
> Notice that you subtract all the evens, and then all the naturals that
> have 3 as a factor, but you've over-subtracted in two ways, as 6 is
> both even and has a factor of 3, so you subtractred for it twice, so
> you add 1 back in, and then you add 2 in because you've subtracted for
> 2 and 3 along the way.

And you subtract 1 for 1, which gives you 4.

Well that's what I get for taking shortcuts.

 
James Harris
http://mathforprofit.blogspot.com/

Quantcast