Re: Prime counting example

From: Proginoskes (proginoskes_at_email.msn.com)
Date: 03/20/05 

Date: 20 Mar 2005 15:25:37 -0800

jstevh@msn.com wrote:
> There are still people trying to claim that my prime counting
> research is not new, so I'd like to give a basic example so that
> critics can try to answer as simply and objectively as possible,
> if they are capable.

I'm not sure how a "basic example" can show that some method is new, or
how you can prove that _anything_ is new. It is possible to prove it's
been done before, and I give a short "alleged" proof that what you're
doing has been done before.

Unless you've changed the algorithm radically, it probably still works,
which is what I think your "basic example" is designed to do. I'm not
arguing ^H^H^H^H^H^H^H^Hlying about that.

> [JSH gives a list of statements which is not sufficient to be
> described as an algorithm; however, you can look up the
> algorithm on the Web or find an earlier thread using
> http://groups-beta.google.com/ .]
> I challenge anyone to show that Legendre's Method works the same way.

I have in front of me two papers:

J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Computing $\pi(x)$:
The Meissel-Lehmer method, Math. Comp. 44 (1985), 537--560.

M. DELEGLISE AND J. RIVAT, "COMPUTING $\pi(x)$: THE MEISSEL, LEHMER,
LAGARIAS, MILLER, ODLYZKO METHOD", MATHEMATICS OF COMPUTATION, Volume
65, Number 213
(January 1996), Pages 235--245.

Your formulas (in an in inefficient form) appear on p. 540 of the
Lagarias paper and p. 236 of the Deleglise and Rivat paper.

The only difference between those formulas and your procedure is that
you don't bother listing the primes in order; you use the a'th positive
integer instead of the a'th prime.

Now, the ball is in your court; explain why your method is different.

> And notice I can give a simple demonstration.
>
> My problem in talking with math people on this subject is a lot of
> emotion as people seem just intent on disagreeing with me without
> regard to the truth.

Or disagreeing with you WITH regard to the truth. (Oops! You forgot to
say 'lying' instead of 'disagreeing'!)

> But hey, it's PRIME NUMBERS.
>
> Why block knowledge in this area for petty personal reasons?
>
> Aren't any of you big enough to just accept what is mathematically
> true?
>
> Oh, I created a Yahoo! Group where you can get an applet that runs
> PrimeCountH.java, so you can see how fast even a minimal
> implementation of these ideas is.

The Meissel-Lehmer-Lagarias-Miller-Odlyzko Method takes time
O(n^(2/3)). What's the running time for your java code?

Just to let you know: The big-O notation used above means that for
large enough n, there are constants C and N such that the
Meissel-Lehmer-Lagarias-Miller-Odlyzko Method to count the number of
primes <= n takes at most C * n^(2/3) operations (loosely, the number
of additions, multiplications, looking up indexed variables, etc), when
n >= N.

In other words, time is not the main objective here, because any
algorithm will run faster on a faster computer. The object here is to
reduce the 2/3 exponent.

> Go to
>
> http://groups.yahoo.com/group/myprimecounting/
>
> Feel free to copy the code and distribute it non-commercially with
> proper attribution.

     --- Christopher Heckman

Relevant Pages