Thursday, June 16, 2005

Counting primes

One of my earlier results comes from a pure thinking exercise on how to count prime numbers as the start is a simple idea: consider a function that gives the count of composites for a particular prime that have that prime as a factor, but no lesser primes as factors.

For instance, up to 10, for 3 that function would give a count of 1, as 9 is the first composite that has 3 as a factor and no lesser primes, while 6 would be excluded as it has 2 as a factor.

Now call that function dS(x,pj) where x is where you're counting up to, and pj is the j_th prime, so my earlier result is dS(10,3) = 1.

Now generalizing a bit, to get the count of composites that have pj as a factor up to and including some x, you can use

floor(x/pj) - 1

where from now on, I'll use [x] = floor(x), so I have

[x/pj] - 1

for the count of composites with pj as a factor.

From that count I need to subtract the number of primes less than pj, which is j-1, so I have

[x/pj] - 1 - (j-1).

Now I need the count of composites up to and including x that have primes less than pj as a factor, which is another function, that is, I now need a function that is the count of composites up to and including some x for all primes less than pj, and I'll use S(x,pj-1), as the count of composites up to and including x that have primes less than pj as factors.

Here's where things are a little tricky as I now have my full dS(x,pj) function as

dS(x,pj) = [x/pj] - 1 - (j-1) - S(x/pj, pj-1)

where S(x/pj, pj-1) is the count of composites that multiply times pj to give a product less than or equal to x, where notice that pj must be less than or equal to sqrt(x) or the composite count given by [x/pj] - 1 will not be correct.

Now I know that in general the count of primes up to and including x is equal to x minus the count of composites minus 1, and that gives an idea for one more function, which I'll call P(x,pj), where

P(x,pj) = [x] - S(x,pj) - 1

which allows me to simplify dS(x, pj) to

dS(x,pj) = P(x/pj,pj-1) - (j-1)

where again pj has to be less than or equal to sqrt(x).

But notice that P(x,pj) is the full count of primes up to and including x, if pj is greater than or equal to the last prime less than sqrt(x), so I can remove all mention of primes with the following

dS(x,y) = (P(x/y,y-1) - P(y-1, sqrt(y-1)))(P(y, sqrt(y)) - P(y-1, sqrt(y-1)))

as if y is not prime then

P(y, sqrt(y)) - P(y-1, sqrt(y-1)) = 0

with the constraint that if y>sqrt(x), then P(x,y) = P(x,sqrt(x)) to keep the correct count.

I also now have

P(x,y) = [x] - S(x,y) - 1

and notice that dS(x,y) is the count of composites that have y as a factor that do not have primes less than y as a factor, which means that if y is composite dS(x,y) = 0, which is how I can remove mention of specific primes.

Now the count of composites for each prime less than or equal to the square root of x when added together just gives the full count of composites, so I have that the S function equals the sum of the dS functions for each prime less than or equal to sqrt(x), where I define S(x,1) = 0, and my prime counting function is complete.

Programming it is rather easy, and yes, it does work!

Though for speed the form where I have specific primes is much faster as otherwise you get recursion that determines that numbers are prime, over and over again, which slows it down.

As an exercise in pure thought, I doubt there are many derivations like it.

There is a surprise in the result in that I get a multi-dimensional prime counting function, which is P(x,y) which gives the same value as the traditional pi(x), if y=sqrt(x).

The other key fact is that dS(x,y) is a partial difference equation.

I came up with the gist of that derivation over three years ago.

James