Harristotelian Logic

For centuries it's been known that the best way to count primes is to first count composites and subtract that number from a total number of positive integers to get your prime count. For instance under 6 you have 5, 4, 3, 2, 1 and 0. Well, by convention we ignore 1 and, of course 0, and there's only one composite, which is 4 = 2(2). And subtracting one for it gives a count of 3, which correspond to 5, 3 and 2.

What's new here is how you count composites.

The way this prime counting function works is amazingly simple and I'll use 7 with N=100 as an example.

You start with floor(100/7) = 14, which tells you that there are 14 products with 7 in them at or below 100. For instance, you have 7(3), 7(11) and, of course, 7(1) included in that count, though 7 is, of course, not a composite. Now you know you have composites from all the primes below 7, which are 2,3,5 and 7, so you subtract 4 to get 10 (more details below). And then you subtract for the number of composites at or below 14, which is 7, to give a count of 3 composites total for 7.

Here's more detail.

The composites counted by subtracting off pi(7,sqrt(7)) are 7*2, 7*3 and 7*5. You also subtract off 7 because the count from floor(100/7) includes it.

Then you subtract off the number of composites below 14 which is 7 as those composites are

7*14, 7*12, 7*10, 7*9, 7*8, 7*6 and 7*4,

which leaves you with 3, which corresponds to

7*7, 7*11 and 7*13.

So you see I went through all the composites formed by multiplying 7 times some integer that are less than or equal to 100.

Notice that you only consider primes below 7 as though floor(100/7) = 14 is too small for there to be composites like 7*7*7, later numbers aren't, and you want that included in your count of composites for 7.

So what about the counts for composites that we subtract off, like 7(2)?

Well, we subtract them off because they've already been counted with the counts for 2, 3, and 5.

Now abstracting out what I just went over the prime counting function then is

pi(x, sqrt(x)) = x - S(x,sqrt(x)) - 1,

where S(x,sqrt(x)) is the sum of dS(x,y) from y = 1 to sqrt(x),

and with only integers,

dS(x,y) = (floor(x/y) - pi(y, sqrt(y)) - S(floor(x/y), y-1))[pi(y+1,sqrt(y+1)) - pi(y-1, sqrt(y-1))].

And abstracting further and adding in dy for "delta y" I have

dS(x, y) = (x/y - pi(y, sqrt(y)) - S(x/y, y-dy))[pi(y+dy, sqrt(y+dy)) - pi(y-dy, sqrt(y-dy))],

where I've dropped the floor() function and introduced dy for "delta y", having, of course, already used dS for "delta S).

Some may have question about continuity about y. It is true that you need to avoid y=0, and I haven't even thought about negative y, so the region of concern is y>0, and to make it even easier for now, I'll stay with y>=1, and do that in reals.

At this point, as we are in discovery mode, it's worth it to go a bit further before going vigorously into the question of continuity.

So rather than handle that question analytically, I'll defer it for now.

That really just leaves S(x/y, y-dy)) and the question of whether or not I have continuity as I let dy approach zero.

I'll leave that for now as well, especially since it's related to the previous.

Ok, then switching to the notation S'_x, S'_y, pi'_x, and pi'_y for the partial differentials since they're a little easier to work with, I have

S'_y(x, y) = (x/y - pi(y, sqrt(y)) - S(x/y, y))pi'_x(y, sqrt(y)).

What's interesting about this is how complicated it is despite looking simple.

However, locked into that single expression is the entire distribution of prime numbers, and if there is indeed a relevance to physics as indicated by some of the work with RH, it may be a fundamental expression that helps define things over a wide range, but that's more of interesting speculation at this point. I like to speculate like that but there's a lot of work to do before I can be absolutely certain.

(Note: For interesting reasons I think you can also use

S'_y(x, y) = (x/y - pi(x, y) - S(x/y, y))pi'_x(y, y).)

Now for some really shallow observations.

First of all, it's a relation between partials versus an easily integrable definition of one.

It turns out that to unravel it, you have to use

pi(x,sqrt(x)) = x - S(x,sqrt(x)) - 1, since from that you have

pi'_x(s,sqrt(x)) = 1 - S'_x(x,sqrt(x)).

Even after you do some initial work there though, you're still stuck with the partial integral of

S(x/y, y) S'_x(y, sqrt(y))

which is a fascinating thing.

It's very fascinating because of how x and y are all mixed up in there.

The nice thing though is that you can get some values, and should be able to get some higher order differentials for a numerical approximation. I just haven't yet felt a strong urge to foray into that territory.

In fact, after realizing one step further for another piece of the integral which requires integration by parts, I stopped thinking about any of it consciously because I needed to digest things.

That was over a month ago.

If you want to think about it, feel free. There may be a Nobel prize in there somewhere, but of course I'd say that. If you're truly interested in knowledge for knowledge's sake, and are extremely confident in your own mathematical abilities then I say, sure, have a go at it. Have fun, and try not to break your brain.

I'm still thinking about the form of the partial differential since though I feel I have the correct form now, I'd just as soon keep thinking, and yes, as far as I know I'm the only person in the world doing that research right now despite the implications of this work.

If you wish to see the prime counting function in action, without a lot of effort, you can use the following Java program to do so.

I should add that several people have posted far faster versions in both Java and C, but I still post this one for those recently introduced to the subject because I think it illustrates things well.

(Use something like

java 100000 true

on the command line to see additional output.)

Thanks for your time and interest.


James Harris

--------------------------------------------------------------------------------------

//Written by James S. Harris. Copyright 2002. All rights reserved.

public class PrimeCountC {


 public static void main(String[] args) {

  long N = Long.parseLong(args[0]);

  PrimeCountC p = new PrimeCountC();

  PrimeCountC.p1 = new PrimeCountC();
  PrimeCountC.p2 = new PrimeCountC();

  if (args.length>1 && args[1].equals("true")) p.printFlag=true;

  long t1 = System.currentTimeMillis();

  int m_max = (int)((Math.sqrt(N)-3)/2)+1;
  System.out.println("m_max="+m_max);

  System.out.println("pi("+N+")="+p.pi(N));

  System.out.println("");

  System.out.println("Time: "+(System.currentTimeMillis() - t1));

 }

 public static PrimeCountC p1, p2;

 public boolean printFlag;

 public String primes="2, ";

 public long pi(long N){

  if (N<9) return N - N/2;

  return (N - N/2 - cCount(N));

 }

 public long cCount(long N){

  if (N<9) return 0;

  int m_max = (int)((Math.sqrt(N)-3)/2)+1;

  return cCount(N, m_max);

 }

 public long cCount(long N, int m_max){

  long S=0;

  long K=0, dS=0;

  byte b=-1;
  for (int c=0; c<m_max; c++){
   if (b==2){
   b=0;
   continue;
      }
   b++;

   if ((p1.pi(2*c+4) - p1.pi(2*c+2))==1){

    K = kCalc(c, N);

    dS = deltaS(c, N);

    S += dS - K;


    if (dS!=0 && printFlag ){


     System.out.println("prime="+(2*c+3)+", dS-K="+(dS-K));

     primes+=(2*c+3)+", ";

     System.out.println("");

    }

   }

  }

  if (printFlag) {

   System.out.println(primes);
   System.out.println("");
   System.out.println("S="+S);
   System.out.println("");
  }

  return S;
 }

 public long deltaS(int m, long N){

  long dS;

  dS = N/(2*m+3) - N/(4*m+6) - p2.pi(2*m+2);

  return dS;


 }

 public long kCalc(int m, long N){

  if (m==0) return 0;

  long k_max, K=0;

  k_max = N/(2*m+3);


  int m_max = (int)((Math.sqrt(k_max)-3)/2)+1;

  if (m>m_max){
    K = p2.cCount(k_max, m_max);
  }
  else{
  byte b=-1;
   for (int j=0; j<m; j++){
  if (b==2){
   b=0;
   continue;
      }
   b++;

    if ((p2.pi(2*j+4) - p2.pi(2*j+2))==1){

     K += p2.deltaS(j, k_max) - p2.kCalc(j, k_max);
    }

   }
  }



  return K;

 }