| Topic: |
Science > Physics |
| User: |
"James Harris" |
| Date: |
27 Aug 2003 09:30:53 AM |
| Object: |
My prime research, focus on a feature |
Repeatedly I've given out a definition for counting prime numbers, but
I'm afraid that something has not been communicated. So first I'm
going to give an example, counting the number of prime numbers up to
100, and afterwards I'll give the function. In that way I hope to
point clearly to a key feature of my research.
What my function does is count the number of composites for each
integer up to the square root of your base number. So for counting
primes up to 100 the base number is 100 and its square root is 10.
Here are the composite counts:
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and summing the dS values gives you 74. Notice when dS equals 0.
Now you add 1 for the number 1, as its not considered prime, and
subtract from 100 to get 25, which is the count of primes up to 100.
And those prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, and 97.
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Some posters have tried to convince you otherwise. While some
apparently have tried to convince you that it doesn't matter if that's
true. Basically I think many of them have just worked to confuse you.
Now here's that definition I've given so many times before:
dS(x,y) = [pi(x/y, y-1) - pi(y-1, sqrt(y-1))]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))],
S(x,1) = 0.
And pi(x, y) = floor(x) - S(x, y) - 1, and you get S as the sum of dS
from dS(x,1) to dS(x,y).
Note: pi(x,sqrt(x)) here gives the same value as the traditional
pi(x).
For faster calculations you need to use
dS(x,y) = [pi(x/y, sqrt(x/y)) - pi(y-1, sqrt(y-1)]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))]
when sqrt(x/y) < y-1.
See http://groups.msn.com/AmateurMath/primecountingfunction.msnw
If your eyes glazed over, or you found yourself wishing to quickly run
away from what looks very complicated then you might understand how
some posters could so easily manipulate the discussion away from the
truth.
The truth is that the dS function does the amazing, as you see a
complete definition above, where you don't see any prime numbers
except 2 but *somehow* as you noticed above dS(x,y) equals 0 when y is
a prime number.
You see, the function *knows* when a number is prime, making it
unique.
Those values from above were
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and you can see the definition I gave above at work, as it picks its
way through the numbers dropping to 0, whenever y is not prime.
That's so huge that I can't emphasize it enough. It's also something
that should give you a certain sadness because what should have
happened is that mathematicians should have excitedly embraced such a
result.
And I think for some of you, disbelieving *me* is easier than
considering even the possibility that a discipline like mathematics
could have enough corruption that mathematicians would fight what they
should be celebrating.
But focusing on me is a mistake.
If you really wish to consider human achievement as some personal
issue, where you wish to make me that powerful as a single human being
that the accomplishments of thousands of years of effort can be
reduced to just being about the individuals involved, then you shatter
the foundations of human civilization, and make it just some fashion
show.
The truth is that the discoveries are more important than the
discoverers, and in letting it turn into some celebrity issue, you
demean human society and its accomplishments.
For some of you I fear that the idea that I might become a celebrity
is all that matters to you. And I fear you think that's all that ever
mattered through all of human history, as if the truth were just a
word, and life has always just been a big popularity contest.
The truth is not just a word and emphasizing truth over social issues
has helped humanity to make the technological achievments which make
my communication through this medium possible.
Where would we be if engineers had paused to figure out who they liked
and disliked before they bothered to use the information discovered?
Mathematicians aren't doing you any favors. I suggest that all of you
focus less on me than on the information, and forget about what
benefits telling the truth will give me, as you consider that the
value to society is far, far greater.
So how can mathematicians behave as they have?
That's an important question, and I suggest we find out why popularity
has so much importance in their world.
James Harris
.
|
|
| User: "Richard Henry" |
|
| Title: Re: My prime research, focus on a feature |
27 Aug 2003 11:01:39 AM |
|
|
"James Harris" <jstevh@msn.com> wrote in message
news:3c65f87.0308270630.34e9ffb3@posting.google.com...
<...>
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
A Real Mathematician told me that in 1963, but he didn't call it His
Function.
<...>
.
|
|
|
| User: "James Harris" |
|
| Title: Re: My prime research, focus on a feature |
27 Aug 2003 06:12:36 PM |
|
|
"Steven" <stevenpantsvh@pandora.be> wrote in message news:<zg63b.2071$pX.126076@phobos.telenet-ops.be>...
Richard Henry wrote:
"James Harris" <jstevh@msn.com> wrote in message
news:3c65f87.0308270630.34e9ffb3@posting.google.com...
<...>
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Can you _prove_ this negative for me please?
(bait = "never" + "entire history")
Well for context it helps if the information you deleted out is given.
What follows is what the poster deleted out, up to the statement on
which focus was placed by that deletion.
What my function does is count the number of composites for each
integer up to the square root of your base number. So for counting
primes up to 100 the base number is 100 and its square root is 10.
Here are the composite counts:
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and summing the dS values gives you 74. Notice when dS equals 0.
Now you add 1 for the number 1, as its not considered prime, and
subtract from 100 to get 25, which is the count of primes up to 100.
And those prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, and 97.
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Ok then, now to that statement, it's amazing but true. Throughout
their *entire* history mathematicians never discovered such a
function.
Obviously, if that were false the easiest thing would be for some
poster to show you something that mathematicians have that does behave
the same way.
But the closest thing they might try works by brute force and
exploiting rounding. I'll see if any try to put it up before I go
into details.
Now notice that the poster deleted out the data, and focused on a
statement which said poster probably figured most of you would simply
reject as being impossible.
But that depends on your faith in the very people I'm explaining to
you aren't living up to that faith.
Remember, math people know that many of you find math either
unappealing or difficult, after all, math people *teach* mathematics.
By pushing you to depend on your trust, deeply ingrained, this poster
showed a fascinating disdain for some of you.
James Harris
.
|
|
|
| User: "Will Twentyman" |
|
| Title: Re: My prime research, focus on a feature |
27 Aug 2003 07:00:27 PM |
|
|
James Harris wrote:
"Steven" <stevenpantsvh@pandora.be> wrote in message news:<zg63b.2071$pX.126076@phobos.telenet-ops.be>...
Richard Henry wrote:
"James Harris" <jstevh@msn.com> wrote in message
news:3c65f87.0308270630.34e9ffb3@posting.google.com...
<...>
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Can you _prove_ this negative for me please?
(bait = "never" + "entire history")
Well for context it helps if the information you deleted out is given.
Ok, so you are going to answer his question about proving mathematicians
never discovered something like dS...
What follows is what the poster deleted out, up to the statement on
which focus was placed by that deletion.
What my function does is count the number of composites for each
integer up to the square root of your base number. So for counting
primes up to 100 the base number is 100 and its square root is 10.
Here are the composite counts:
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and summing the dS values gives you 74. Notice when dS equals 0.
Now you add 1 for the number 1, as its not considered prime, and
subtract from 100 to get 25, which is the count of primes up to 100.
And those prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, and 97.
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Ok then, now to that statement, it's amazing but true. Throughout
their *entire* history mathematicians never discovered such a
function.
Obviously, if that were false the easiest thing would be for some
poster to show you something that mathematicians have that does behave
the same way.
But that doesn't show that it's true. Only that it's (presumably) easy
for us to show it false.
But the closest thing they might try works by brute force and
exploiting rounding. I'll see if any try to put it up before I go
into details.
Now notice that the poster deleted out the data, and focused on a
statement which said poster probably figured most of you would simply
reject as being impossible.
But that depends on your faith in the very people I'm explaining to
you aren't living up to that faith.
Remember, math people know that many of you find math either
unappealing or difficult, after all, math people *teach* mathematics.
By pushing you to depend on your trust, deeply ingrained, this poster
showed a fascinating disdain for some of you.
James Harris
But, can you, for that matter *will* you, prove that no mathematician
came up with anything like your dS? You didn't answer the question,
just showed us what the function is and talked about methods of disproof.
--
Will Twentyman
email: wtwentyman at copper dot net
.
|
|
|
|
|
|
| User: "Richard Henry" |
|
| Title: Re: My prime research, focus on a feature |
28 Aug 2003 02:20:58 AM |
|
|
"Tralfaz" <tralfaz@takeaguess.com> wrote in message
news:3f4c5562_4@newsfeed...
How many numbers less than 100 are divisible by 2?
100/2 = 50
How many numbers less than 100 are divisible by 3?
100/3 = 33
How many numbers less than 100 are divisible by 2 or 3?
100/2 + 100/3 - 100/6 = 50 + 33 - 16 = 66
Interesting. You ust have MS Calculator installed on your machine.
.
|
|
|
|
| User: "Christoph M. Wintersteiger" |
|
| Title: Re: My prime research, focus on a feature |
31 Aug 2003 08:20:59 AM |
|
|
Hello there. I'm new here, and already found out that James Harris is
working hard in the field of number theory. Well, so am I, although
not from a mathematical point of view, but from a computer scientists
view.
The dS function J.H. gave - be it correct or not - is sure an
interesting one, but from the point of complexity it is of no
practical use whatsoever, because when analyzing bigger numbers, the
complexity skyrockets and calculations would take way too long to be
of any use.
Just for the sake of it I give you another example my research work
has yielded: The limit of the function a(t) = floor(X/ceil(X/a(t-1))
with t going to infinity, yields a factor of (the integer) X.
Might sound remarkable, but when you express it in terms of a
programming language, it prooves to be the same as the trivial
division algorithm - one of the worst known, in terms of complexity.
I'm not trying to discourage anyone, just encouraging you to speed
things up ;-)
Thanks for reading,
CM Wintersteiger
(Excuse my bad english, I'm german.)
On 27 Aug 2003 07:30:53 -0700, (James Harris) wrote:
Repeatedly I've given out a definition for counting prime numbers, but
I'm afraid that something has not been communicated. So first I'm
going to give an example, counting the number of prime numbers up to
100, and afterwards I'll give the function. In that way I hope to
point clearly to a key feature of my research.
What my function does is count the number of composites for each
integer up to the square root of your base number. So for counting
primes up to 100 the base number is 100 and its square root is 10.
Here are the composite counts:
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and summing the dS values gives you 74. Notice when dS equals 0.
Now you add 1 for the number 1, as its not considered prime, and
subtract from 100 to get 25, which is the count of primes up to 100.
And those prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, and 97.
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Some posters have tried to convince you otherwise. While some
apparently have tried to convince you that it doesn't matter if that's
true. Basically I think many of them have just worked to confuse you.
Now here's that definition I've given so many times before:
dS(x,y) = [pi(x/y, y-1) - pi(y-1, sqrt(y-1))]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))],
S(x,1) = 0.
And pi(x, y) = floor(x) - S(x, y) - 1, and you get S as the sum of dS
from dS(x,1) to dS(x,y).
Note: pi(x,sqrt(x)) here gives the same value as the traditional
pi(x).
For faster calculations you need to use
dS(x,y) = [pi(x/y, sqrt(x/y)) - pi(y-1, sqrt(y-1)]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))]
when sqrt(x/y) < y-1.
See http://groups.msn.com/AmateurMath/primecountingfunction.msnw
If your eyes glazed over, or you found yourself wishing to quickly run
away from what looks very complicated then you might understand how
some posters could so easily manipulate the discussion away from the
truth.
The truth is that the dS function does the amazing, as you see a
complete definition above, where you don't see any prime numbers
except 2 but *somehow* as you noticed above dS(x,y) equals 0 when y is
a prime number.
You see, the function *knows* when a number is prime, making it
unique.
Those values from above were
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and you can see the definition I gave above at work, as it picks its
way through the numbers dropping to 0, whenever y is not prime.
That's so huge that I can't emphasize it enough. It's also something
that should give you a certain sadness because what should have
happened is that mathematicians should have excitedly embraced such a
result.
And I think for some of you, disbelieving *me* is easier than
considering even the possibility that a discipline like mathematics
could have enough corruption that mathematicians would fight what they
should be celebrating.
But focusing on me is a mistake.
If you really wish to consider human achievement as some personal
issue, where you wish to make me that powerful as a single human being
that the accomplishments of thousands of years of effort can be
reduced to just being about the individuals involved, then you shatter
the foundations of human civilization, and make it just some fashion
show.
The truth is that the discoveries are more important than the
discoverers, and in letting it turn into some celebrity issue, you
demean human society and its accomplishments.
For some of you I fear that the idea that I might become a celebrity
is all that matters to you. And I fear you think that's all that ever
mattered through all of human history, as if the truth were just a
word, and life has always just been a big popularity contest.
The truth is not just a word and emphasizing truth over social issues
has helped humanity to make the technological achievments which make
my communication through this medium possible.
Where would we be if engineers had paused to figure out who they liked
and disliked before they bothered to use the information discovered?
Mathematicians aren't doing you any favors. I suggest that all of you
focus less on me than on the information, and forget about what
benefits telling the truth will give me, as you consider that the
value to society is far, far greater.
So how can mathematicians behave as they have?
That's an important question, and I suggest we find out why popularity
has so much importance in their world.
James Harris
.
|
|
|
|
| User: "Uncle Al" |
|
| Title: Re: My prime research, focus on a feature |
27 Aug 2003 12:04:17 PM |
|
|
James Harris wrote:
Repeatedly I've given out a definition for counting prime numbers,
[snuip]
and been made an utter fool by competent folks who trivially refute
your psychotic spews with concrete counterexamples that you ignore.
http://w0rli.home.att.net/youare.swf
http://www.mazepath.com/uncleal/sunshine.jpg
--
Uncle Al
http://www.mazepath.com/uncleal/eotvos.htm
(Do something naughty to physics)
.
|
|
|
|
| User: "Will Twentyman" |
|
| Title: Re: [JSH] My prime research, focus on a feature |
27 Aug 2003 10:26:59 AM |
|
|
James Harris wrote:
Repeatedly I've given out a definition for counting prime numbers, but
I'm afraid that something has not been communicated. So first I'm
going to give an example, counting the number of prime numbers up to
100, and afterwards I'll give the function. In that way I hope to
point clearly to a key feature of my research.
What my function does is count the number of composites for each
integer up to the square root of your base number. So for counting
primes up to 100 the base number is 100 and its square root is 10.
Here are the composite counts:
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and summing the dS values gives you 74. Notice when dS equals 0.
Now you add 1 for the number 1, as its not considered prime, and
subtract from 100 to get 25, which is the count of primes up to 100.
And those prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, and 97.
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Some posters have tried to convince you otherwise. While some
apparently have tried to convince you that it doesn't matter if that's
true. Basically I think many of them have just worked to confuse you.
Now here's that definition I've given so many times before:
dS(x,y) = [pi(x/y, y-1) - pi(y-1, sqrt(y-1))]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))],
S(x,1) = 0.
And pi(x, y) = floor(x) - S(x, y) - 1, and you get S as the sum of dS
from dS(x,1) to dS(x,y).
Note: pi(x,sqrt(x)) here gives the same value as the traditional
pi(x).
For faster calculations you need to use
dS(x,y) = [pi(x/y, sqrt(x/y)) - pi(y-1, sqrt(y-1)]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))]
when sqrt(x/y) < y-1.
I am not going to argue with the correctness of your results. A point
of curiousity about this method is, how efficient is it (in terms of
big-O notation)? If your new algorithm is considerably slower than
existing algorithms, it is only a curiousity. If it is faster, then you
have done something worthy of note.
See http://groups.msn.com/AmateurMath/primecountingfunction.msnw
This would be the site I can only see when I'm not logged into my msn
passport.
If your eyes glazed over, or you found yourself wishing to quickly run
away from what looks very complicated then you might understand how
some posters could so easily manipulate the discussion away from the
truth.
The truth is that the dS function does the amazing, as you see a
complete definition above, where you don't see any prime numbers
except 2 but *somehow* as you noticed above dS(x,y) equals 0 when y is
a prime number.
You see, the function *knows* when a number is prime, making it
unique.
Those values from above were
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and you can see the definition I gave above at work, as it picks its
way through the numbers dropping to 0, whenever y is not prime.
That's so huge that I can't emphasize it enough. It's also something
that should give you a certain sadness because what should have
happened is that mathematicians should have excitedly embraced such a
result.
You haven't stated *why* it's exciting. You have a new method of
counting primes. That is not, in itself, exciting. How fast is your
method? Does dS return 0 for composites faster than checking whether a
number is composite by other methods?
Note: these are not questions I have the answer to, these are the
questions that will help determine the value of this work.
[non mathematics deleted.]
--
Will Twentyman
email: wtwentyman at copper dot net
.
|
|
|
| User: "Christian Bau" |
|
| Title: Re: [JSH] My prime research, focus on a feature |
27 Aug 2003 02:06:05 PM |
|
|
In article <3f4b7bdc_3@newsfeed>,
Will Twentyman <wtwentyman@read.my.sig> wrote:
James Harris wrote:
Repeatedly I've given out a definition for counting prime numbers, but
I'm afraid that something has not been communicated. So first I'm
going to give an example, counting the number of prime numbers up to
100, and afterwards I'll give the function. In that way I hope to
point clearly to a key feature of my research.
What my function does is count the number of composites for each
integer up to the square root of your base number. So for counting
primes up to 100 the base number is 100 and its square root is 10.
Here are the composite counts:
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and summing the dS values gives you 74. Notice when dS equals 0.
Now you add 1 for the number 1, as its not considered prime, and
subtract from 100 to get 25, which is the count of primes up to 100.
And those prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, and 97.
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Some posters have tried to convince you otherwise. While some
apparently have tried to convince you that it doesn't matter if that's
true. Basically I think many of them have just worked to confuse you.
Now here's that definition I've given so many times before:
dS(x,y) = [pi(x/y, y-1) - pi(y-1, sqrt(y-1))]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))],
S(x,1) = 0.
And pi(x, y) = floor(x) - S(x, y) - 1, and you get S as the sum of dS
from dS(x,1) to dS(x,y).
Note: pi(x,sqrt(x)) here gives the same value as the traditional
pi(x).
For faster calculations you need to use
dS(x,y) = [pi(x/y, sqrt(x/y)) - pi(y-1, sqrt(y-1)]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))]
when sqrt(x/y) < y-1.
I am not going to argue with the correctness of your results. A point
of curiousity about this method is, how efficient is it (in terms of
big-O notation)? If your new algorithm is considerably slower than
existing algorithms, it is only a curiousity. If it is faster, then you
have done something worthy of note.
It is just old Legendre's formula, slightly repacked.
Legendre defined
phi (x, k) := number of positive integers <= x which are not
divisible by any of the first k primes.
You get phi (x, 0) = x for all x, and if k > 0 then
phi (x, k) = 0 if x = 0
phi (x, k) = 1 if 1 <= x < p (k+1), where p(k+1) is the (k+1)st prime
phi (x, k) = pi (x) - k + 1 if p(k) <= x < (p(k+1))^2
and from the last equation it follows that with k = pi (x^(1/2))
pi (x) = phi (x, k) + k - 1
And then there is the recursion formula
phi (x, k) = phi (x, k-1) - phi (x/p(k), k-1).
That one is quite obvious because the difference between phi (x, k) and
phi (x, k-1) are exactly those integers <= x with p(k) as the smallest
prime factor, and these integers can be written as y*p(k), where y has
no divisor <= p(k) and y <= x / p(k).
I think you can figure out easily how phi (x, k) and his function dS (x,
y) are related. Execution time is O (N). Meissel's algorithm is a
trivial variation of this; if you take the first recursion level of
Legendre's formula then you will see that you end up calculating many
values pi (x') where x' <= x^(2/3). You can get all those by using a
sieve in O (N^(2/3)), and the remaining work is done in O (N / log^3 N),
I think; so this is quite simple and much much faster.
Btw. I wonder if he ever figured out the cute trick how to calculate phi
(x, k) for lets say k <= 6 and arbitrarily large x using just one
division and two multiplications. I don't know if Meissel knew it, but
Lehmer certainly did.
.
|
|
|
| User: "Will Twentyman" |
|
| Title: Re: [JSH] My prime research, focus on a feature |
27 Aug 2003 02:40:41 PM |
|
|
Christian Bau wrote:
In article <3f4b7bdc_3@newsfeed>,
Will Twentyman <wtwentyman@read.my.sig> wrote:
James Harris wrote:
Repeatedly I've given out a definition for counting prime numbers, but
I'm afraid that something has not been communicated. So first I'm
going to give an example, counting the number of prime numbers up to
100, and afterwards I'll give the function. In that way I hope to
point clearly to a key feature of my research.
What my function does is count the number of composites for each
integer up to the square root of your base number. So for counting
primes up to 100 the base number is 100 and its square root is 10.
Here are the composite counts:
dS(100,2) = 49; dS(100,3) = 16; dS(100,4) = 0;
dS(100,5) = 6; dS(100,7) = 3; dS(100,8) = 0;
dS(100,9) = 0; dS(100,10)= 0;
and summing the dS values gives you 74. Notice when dS equals 0.
Now you add 1 for the number 1, as its not considered prime, and
subtract from 100 to get 25, which is the count of primes up to 100.
And those prime numbers are
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, and 97.
Now a key feature of dS that I want to emphasize is that for dS(x,y)
if y is not prime dS equals 0. I want to repeat that for emphasis,
for dS(x,y) if y is not prime dS equals 0.
Amazingly enough, mathematicians never discovered such a function as
my dS throughout their entire history.
Some posters have tried to convince you otherwise. While some
apparently have tried to convince you that it doesn't matter if that's
true. Basically I think many of them have just worked to confuse you.
Now here's that definition I've given so many times before:
dS(x,y) = [pi(x/y, y-1) - pi(y-1, sqrt(y-1))]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))],
S(x,1) = 0.
And pi(x, y) = floor(x) - S(x, y) - 1, and you get S as the sum of dS
from dS(x,1) to dS(x,y).
Note: pi(x,sqrt(x)) here gives the same value as the traditional
pi(x).
For faster calculations you need to use
dS(x,y) = [pi(x/y, sqrt(x/y)) - pi(y-1, sqrt(y-1)]
[pi(y, sqrt(y)) - pi(y-1, sqrt(y-1))]
when sqrt(x/y) < y-1.
I am not going to argue with the correctness of your results. A point
of curiousity about this method is, how efficient is it (in terms of
big-O notation)? If your new algorithm is considerably slower than
existing algorithms, it is only a curiousity. If it is faster, then you
have done something worthy of note.
It is just old Legendre's formula, slightly repacked.
Legendre defined
phi (x, k) := number of positive integers <= x which are not
divisible by any of the first k primes.
You get phi (x, 0) = x for all x, and if k > 0 then
phi (x, k) = 0 if x = 0
phi (x, k) = 1 if 1 <= x < p (k+1), where p(k+1) is the (k+1)st prime
phi (x, k) = pi (x) - k + 1 if p(k) <= x < (p(k+1))^2
and from the last equation it follows that with k = pi (x^(1/2))
pi (x) = phi (x, k) + k - 1
And then there is the recursion formula
phi (x, k) = phi (x, k-1) - phi (x/p(k), k-1).
That one is quite obvious because the difference between phi (x, k) and
phi (x, k-1) are exactly those integers <= x with p(k) as the smallest
prime factor, and these integers can be written as y*p(k), where y has
no divisor <= p(k) and y <= x / p(k).
I think you can figure out easily how phi (x, k) and his function dS (x,
y) are related. Execution time is O (N). Meissel's algorithm is a
trivial variation of this; if you take the first recursion level of
Legendre's formula then you will see that you end up calculating many
values pi (x') where x' <= x^(2/3). You can get all those by using a
sieve in O (N^(2/3)), and the remaining work is done in O (N / log^3 N),
I think; so this is quite simple and much much faster.
And with this, I believe, we arrive at why James is not getting the
attention he feels he deserves. His algorithm does not get us to our
primes any faster. It is slower than existing algorithms, and therefore
a curiousity.
Btw. I wonder if he ever figured out the cute trick how to calculate phi
(x, k) for lets say k <= 6 and arbitrarily large x using just one
division and two multiplications. I don't know if Meissel knew it, but
Lehmer certainly did.
--
Will Twentyman
email: wtwentyman at copper dot net
.
|
|
|
|
|
|
|
Related Articles |
|
|
