Harristotelian Logic

Posters lie to you all the time about my research and one of the most telling areas is with my prime counting function.

I've talked recently about the sieve form giving the LaTex as that can give you a better look at it, if you paste it somewhere where you can process LaTex:

With natural numbers x and n, where p_i is the i_th prime:

:<math>P(x,n) = x - 1 -\sum_{i=1}^n {(P(x/p_i,i-1) - (i-1))}</math>

where if n is greater than the count of primes up to and including <math>\sqrt{x}</math> then n is reset to that count.

One correction I have to make to what I've said previously on this subject is that it is true that solving that expression out explicitly will give the same expression as Legendre's Method.

It does.

So no, the simple expression even in its sieve form is not going to be fast, but the first speed-up is to not iterate from i=1, as that covers evens. Here's a faster version:

With natural numbers x and n, where p_i is the i_th prime:

:<math>P(x,n) = floor(x/2) -\sum_{i=2}^n {(P(x/p_i,i-1) - (i-1))}</math>

where if n is greater than the count of primes up to and including <math>\sqrt{x}</math> then n is reset to that count.

Now that makes it quite a bit more than twice as fast. Now I posted recently that the sieve form was fast, as I haven't played with this all for some time, and I always would correct out the evens, and it IS fast if you do that simple thing.

But it doesn't stop there. It turns out that the iteration at i=2 can be given by

floor((x-3)/6)

so you can do yet another speed up by using:

With natural numbers x and n, where p_i is the i_th prime:

:<math>P(x,n) = floor(x/2) - floor((x-3)/6) - \sum_{i=3}^n {(P(x/p_i,i-1) - (i-1))}</math>

where if n is greater than the count of primes up to and including <math>\sqrt{x}</math> then n is reset to that count.

And those of you who bother to try that out—hoping I got the math right on that last, I think I did—will find that it is far faster than Legendre's Method can be made to be.

So what's the point here?

I made some mistakes in talking about an area I haven't delved into for years, as I got bored with the speed issue, and some posters maintained one thing based on exploiting my mistakes, when the mathematical reality—the full story—wasn't too far away.

So why do those slight changes make for very fast prime counting?

They don't care. They don't care to let you know about those changes. They don't care what the mathematical reality is.

My research covers a lot of ground, and I often forget details about it, as I go away from one particular area for years, so I do apologize for getting some of the facts wrong.

But I'll come back and correct. I knew there were fast ways to count primes from my idea, so it was just a matter of getting the details right.

The people I'm facing, well, I think for them it's just a game, where a lot of times you don't even know who they are as they're using pseudonyms, and clearly think that they can never be held accountable for what they say on Usenet.