Thursday, July 25, 2002
Counting prime numbers, rev
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.
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;
}
# posted by James Harris @ 02:42
Thursday, July 18, 2002
Factoring large numbers, breaking RSA?
I spent seven years looking for a short proof of Fermat's Last Theorem, and felt relief when I finally found it because I thought mathematicians couldn't ignore such a cool thing when it was right in front of them.
I was wrong.
Then I found a new prime counting function, and discovered that what people had written as pi(x) was really a three dimensional function better represented by pi(x,y). More importantly the prime counting function in its difference form was simple enough for even a kid to understand, and as a differential the implications for research in both mathematics and physics were so huge that I again felt relieved,
as I thought mathematicians and physicists couldn't ignore such a wonderful discovery that could make their lives so much easier.
But I was wrong again.
It occurs to me that the only discovery I can make that won't be ignored is a way to break RSA in a couple of hours on a personal pc.
I've done more research on that since a few wild guesses years ago, and I have a Java program that factors 64 bit numbers in only a few minutes; however, I stopped playing with it because it was still way to slow to even tackle a 512 bit number, and because I debated the wisdom of such research.
You see, if I do figure out a short, simple way to factor large numbers then RSA is gone. I will post that information as I have done with everything else, which will force everyone to switch from RSA.
But that would take time.
In that time more than you realize would be vulnerable to anyone who had access to the Internet and had the method.
I decided that it wasn't worth it to me to figure something like that out, but I'm beginning to question my conclusions.
You see, if the world of physics and mathematics is as bad as it appears to me now, then maybe things in other areas are worse than we know, and the world might be better off finding that out now because of some financial crunch than finding it out later.
So, I will post my latest research in the form of a Java program I call Exper13.java later today. Then I will begin again to look for a very fast factoring method, and will not stop until I succeed in finding one that will allow anyone with a personal pc to break RSA, and thus break all encryption based on it worldwide.
It's mind boggling to me that the only way I can stop the lies is to find something that mathematicians can't lie about or ignore because it won't change anything if they do.
If they ignore the discovery when I make it, then the banks will be vulnerable until billions of dollars just float away, and people have to pay attention.
It's your choice though, still.
The program I mention is NOT the answer to that problem, but just an initial effort by me. It MAY have ideas in it that could help someone else solve the problem now, but probably it does not. It may just be a useless idea for the big problem, and I may have to find some other way after I figure that out.
In a word, it's a gamble.
I feel I have no choice, and nothing to lose at this point.
I'll post the program in eight hours.
I was wrong.
Then I found a new prime counting function, and discovered that what people had written as pi(x) was really a three dimensional function better represented by pi(x,y). More importantly the prime counting function in its difference form was simple enough for even a kid to understand, and as a differential the implications for research in both mathematics and physics were so huge that I again felt relieved,
as I thought mathematicians and physicists couldn't ignore such a wonderful discovery that could make their lives so much easier.
But I was wrong again.
It occurs to me that the only discovery I can make that won't be ignored is a way to break RSA in a couple of hours on a personal pc.
I've done more research on that since a few wild guesses years ago, and I have a Java program that factors 64 bit numbers in only a few minutes; however, I stopped playing with it because it was still way to slow to even tackle a 512 bit number, and because I debated the wisdom of such research.
You see, if I do figure out a short, simple way to factor large numbers then RSA is gone. I will post that information as I have done with everything else, which will force everyone to switch from RSA.
But that would take time.
In that time more than you realize would be vulnerable to anyone who had access to the Internet and had the method.
I decided that it wasn't worth it to me to figure something like that out, but I'm beginning to question my conclusions.
You see, if the world of physics and mathematics is as bad as it appears to me now, then maybe things in other areas are worse than we know, and the world might be better off finding that out now because of some financial crunch than finding it out later.
So, I will post my latest research in the form of a Java program I call Exper13.java later today. Then I will begin again to look for a very fast factoring method, and will not stop until I succeed in finding one that will allow anyone with a personal pc to break RSA, and thus break all encryption based on it worldwide.
It's mind boggling to me that the only way I can stop the lies is to find something that mathematicians can't lie about or ignore because it won't change anything if they do.
If they ignore the discovery when I make it, then the banks will be vulnerable until billions of dollars just float away, and people have to pay attention.
It's your choice though, still.
The program I mention is NOT the answer to that problem, but just an initial effort by me. It MAY have ideas in it that could help someone else solve the problem now, but probably it does not. It may just be a useless idea for the big problem, and I may have to find some other way after I figure that out.
In a word, it's a gamble.
I feel I have no choice, and nothing to lose at this point.
I'll post the program in eight hours.
# posted by James Harris @ 13:23
Wednesday, July 17, 2002
JSH: Pointing out the obvious
One of the side effects of my posting everything as I figure things out is that it makes scientists and mathematicians look worse.
So there's this thing called the Riemann Hypothesis, or RH, and I'm slowly working my way through dealing with it, while being completely ignored by Ph.d's the world thinks are highly intelligent.
There's only one way this can go folks, which is that those Ph.d's lose more the longer they ignore me.
(Do I lose anything? Maybe it will be up to various courts around the world to decide. How many of you want to find yourself in a courtroom, if you're in America, "taking the Fifth" so you don't have to admit even seeing my prime counting function? )
That makes sense because if you were objective, and more concerned about the truth, you'd find yourselves getting increasingly frustrated and as time continued to go by, outraged.
Why?
Because you probably have a lot of respect for these people, and you think highly of them, so the longer they sit on their duffs using their positions to ignore valuable work, the more likely it will be that those positions are diminished.
And some of you would like to have some of that respect yourselves someday, as although you're graduate students or lowly post-docs now, you hope to take your place at the helm someday and maybe make your own great discovery.
But now you're looking at the prospect of a world that will cast a cynical eye on your "discovery", and at a process that could take much longer, while you work harder both to prove that your work is correct, and that it is valuable.
Folks, a side effect of my posting as I go is the falling of the world's latest priesthood.
(Now do you get it? See why I keep telling you the Universe has a sense of humor?)
That's the point above my interests, which is to bring down the scientific and mathematical priesthoods…to bring them down to their bellies.
You see, that priesthood, like many priesthoods before it, has gotten high on its beliefs about itself, rather with being obsessed with the truth, and it's taken its worship of itself to the extreme of believing it is more important than the truth to the extent of trying to keep the truth from being known, through inaction..
Look at the headlines folks, the trail is leading to your heroes, and they're failing as it was expected they would.
Many of you have put in a lot of time and effort over years in your pursuit of your goals. I'm telling you that your ability to attain those goals could be negatively affected right now.
Come on people! Why should I have to remind you of selfish reasons to get you to tell the truth?
So there's this thing called the Riemann Hypothesis, or RH, and I'm slowly working my way through dealing with it, while being completely ignored by Ph.d's the world thinks are highly intelligent.
There's only one way this can go folks, which is that those Ph.d's lose more the longer they ignore me.
(Do I lose anything? Maybe it will be up to various courts around the world to decide. How many of you want to find yourself in a courtroom, if you're in America, "taking the Fifth" so you don't have to admit even seeing my prime counting function? )
That makes sense because if you were objective, and more concerned about the truth, you'd find yourselves getting increasingly frustrated and as time continued to go by, outraged.
Why?
Because you probably have a lot of respect for these people, and you think highly of them, so the longer they sit on their duffs using their positions to ignore valuable work, the more likely it will be that those positions are diminished.
And some of you would like to have some of that respect yourselves someday, as although you're graduate students or lowly post-docs now, you hope to take your place at the helm someday and maybe make your own great discovery.
But now you're looking at the prospect of a world that will cast a cynical eye on your "discovery", and at a process that could take much longer, while you work harder both to prove that your work is correct, and that it is valuable.
Folks, a side effect of my posting as I go is the falling of the world's latest priesthood.
(Now do you get it? See why I keep telling you the Universe has a sense of humor?)
That's the point above my interests, which is to bring down the scientific and mathematical priesthoods…to bring them down to their bellies.
You see, that priesthood, like many priesthoods before it, has gotten high on its beliefs about itself, rather with being obsessed with the truth, and it's taken its worship of itself to the extreme of believing it is more important than the truth to the extent of trying to keep the truth from being known, through inaction..
Look at the headlines folks, the trail is leading to your heroes, and they're failing as it was expected they would.
Many of you have put in a lot of time and effort over years in your pursuit of your goals. I'm telling you that your ability to attain those goals could be negatively affected right now.
Come on people! Why should I have to remind you of selfish reasons to get you to tell the truth?
# posted by James Harris @ 08:27
