Re: Computational complexity, number theory tidbits

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

Date: 3 Aug 2004 07:59:06 -0700

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

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.

That's the inclusion-exclusion, as you end up subtracting and adding
back in to correct your count, but at the the end you get a count of
primes.

>
> *warning: sloppy notation... someone should write a newsreader that
> can interpret LaTeX. *
>
> [N] - sum([N/p_i]) + sum([N/(p_j*p_i)]) - sum([N/(p_k*p_j*p_i)]) + ...
>
> The method can be written as (by extracting the p = 2 cases):
>
> [N] - [N/2] - sum([N/p_i]) + sum([N/(2*p_i)]) + sum([N/(p_j*p_i)]) -
> sum([N/(2*p_j*p_i)]) - sum([N/(p_k*p_j*p_i)]) + ...
>
> Now combing the terms with the above relation:
>
> [(N+1)/2] - sum([(N+p_i)/(2*p_i)]) + sum([(N+p_j*p_i)/(2*p_j*p_i)]) -
> sum([(N-p_k*p_j*p_i)/(2*p_k*p_j*p_i)]) + ...

If that's correct then you may have just written a far faster
alternate to Legendre's which I'd think would be worth publication.

Can somone out there code it and see how fast it is?
 
> >And hey, I'll admit it, I didn't know that pattern was there, and I'm
> >finally a bit curious here.
> >
> >What, did you find it in a textbook or something?
>
> No, I just noticed the relation at the top.

I'd be interested in a proof of that relation.

Note that for the relations I gave I proved [(N-4)/6] directly by the
method I've posted, and then used it with my prime counting function
to find the other formulas.

So, not surprisingly, I'm curious about how you came up with your
formula, as I doubt you used my prime counting function.

That is, I'd like to see the proof of your formula:

[(N+k)/(2*k)] = [N/k] - [N/(2*k)]

And I'd prefer it if certain posters who've continued to post in these
threads with some odd posts with mathematical assertions that don't
stand up to scrutiny would try to hold off, for once.

Specifically I'm talking about C. Bond and *** Winter.

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

Quantcast