Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime counting function- no error.

  1. Oct 3, 2005 #1
    Prime counting function-- no error.

    I have developed a prime counting function with no error; it returns the exact number of primes equal to or less than any number one chooses.

    I am rather ignorant of progress in this field... Has this been done before? Please, ignore any skepticism you might have about my claim; even if were somehow wrong, I would still like to know if such a function is already in existence.

    (edit) Note: This function does not require any list of primes or knowledge of the "nth prime number". It does not utilize any functions that are not valid, known, and easily computable.
     
    Last edited: Oct 3, 2005
  2. jcsd
  3. Oct 3, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Of course it can be found exactly, a basic sieve of Eratosthenes will do this. It can even be found exactly without explicitly making a list of all primes up to x (Meissel's and variants).

    I'm possibly unfairly wary of your claim of "easily computable". We've had claims here before of being able to compute pi(x) in constant time, so I'll give you a chance to explain before becoming too judgemental. You might want to look at http://mathworld.wolfram.com/PrimeCountingFunction.html and compare your algorithms complexity with the ones listed.
     
  4. Oct 3, 2005 #3
    Mm... Well, the functions utilized within the larger function are easily computable (what I meant in saying so before was only that I haven't utilized any difficult functions that are defined by an algorithm and not a formula, and that everything I've done is "easily" computable, not necessarily "quickly"); the overall thing will become rather time-consuming as the numbers involve get longer. In practice, it wouldn't be very useful as a quick calculation, but it is exact.

    I certainly don't have anything that can be computed in constant time. I would have to wonder if that would even be possible...

    And has the sieve of Eratosthenes been written as an explicit mathematical function, or only as an abstract algorithm?

    (edit) Many, if not all, of the methods for computation on that site depend on knowledge of the nth prime... I wasn't aware of any function that gives this value, or at least not through a method of practical complexity. It's common use, though, would indicate that there is...?
     
    Last edited: Oct 3, 2005
  5. Oct 3, 2005 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    It's a very computable thing. No different than if you wanted log(4506) to 5 decimal places.

    There are unwieldy asymptotics for the nth prime, but the use of [tex]p_n[/tex] in the algorithms you saw there is a notational one. If you look at Meissel's basic formula it involves a sum over the primes less than sqrt(x), the time it will take to find these will be inconsequential to the overall time of the algorithm. You might want to look at some of the papers at

    http://www.dtc.umn.edu/~odlyzko/doc/cnt.html

    where they have a very improved variant of Meissel's as well as a nifty "analytic" method.
     
  6. Oct 3, 2005 #5
    Thank you. I'll have to look at that.
     
  7. Oct 3, 2005 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    How fast is your function? Can you count the primes up to, say, 10^20 for us with your formula?
     
  8. Oct 4, 2005 #7
    Congratulations - can you tell us the number it returns for the largest known prime 2^25964951-1

    By the way above prime has 7816230 decicimal digitits
     
  9. Oct 5, 2005 #8

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    I'm sure you know that the current best algorithms can't come anywhere near finding pi(2^25964951-1) in what could be considered a "reasonable" amount of time.

    A claim of an algorithm for computing pi(x) exactly is not an unreasonable thing, I've mentioned a few methods in this thread. What is most interesting (assuming the method is correct) is both it's speed and whether the approach is novel in some way. Of course there's no way to judge any of these criterea without seeing the proposed method.
     
  10. Oct 9, 2005 #9
    Yes, I assume that mine is not any sort of a breakthrough. I lack any software to run it efficiently, though, so I really can't test to see how fast it does run.

    I have a formula for the nth prime, as well (actually, I have a formula for the product series of all primes 1 through [tex]\pi (w)[/tex], and I have one trivial equation to work out in order to complete the formula for the nth prime)-- this one is insanely inefficent, and I'm sure there are infinitely better ones, but it was still interesting to make.

    Might you have any suggestions as far as mathematics software goes?

    Note: By "inefficent" I mean that it will take a long time to calculate, not that it is in any way inaccurate.
     
    Last edited: Oct 9, 2005
  11. Oct 9, 2005 #10
    What is your algorithm?
     
  12. Oct 8, 2009 #11
    Re: Prime counting function-- no error.

    I can also compute pi(x) exactly without finding ANY primes smaller than x or sqr(x). It also do not require successive division by primes or the value of a previous pi (y) for y < x. The terms are required to be computed like in:

    max {n in IN : 5*7 + 6*5*7(n-1) <= x}

    and uses only four constants, all discardable. This is equivalent to computing:

    floor ((x - 5*7 + 6*5*7)/6*5*7).

    There are many terms however. The formula coefficients needs to be computed and stored in memory.

    The method is much simpler than Extended Meissel-Lehmer algorithm but requires more storage space for large x. The storage requirement is of order:

    b_4 = 4
    b_n = b_(n-1) + n -1

    for large n. Can this be written in big O notation?o:):surprised
     
  13. Oct 8, 2009 #12

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Re: Prime counting function-- no error.

    It's O(n^2) -- actually, b(n) = (n^2 - n - 4) / 2.

    That's a huge amount of memory, though. Every time I start Pari it calculates the primes up to a trillion (taking maybe 1-2 seconds). If your memory is in bits, this size calculation would take 56,000 terabytes!
     
  14. Oct 10, 2009 #13
    Re: Prime counting function-- no error.

    Thank you. It looks totally impractical then. Just sending it through a register will take 35925 days at 25M per second.

    I will post the formula compution method somwhere. The formula can be studied statisticly (distribution of coefficients). There are terms that may be zero if computed in the sets congruent to 1 (mod 6) or 5 (mod 6) and they may be predictable.

    Maybe someone can fit more powerfull ideas to it or find the complement calculation of it (it counts composites). Maybe it is not so useless theoretically and can be used in proofs.

    How is O(n^(1/2 + e)) for any e > 0 a better upper bound than O(n^2) - doesn't it mean the storage is <= Cn^(1/2 + 1/1000) or Cn^(1/2 + 1000) or ...
     
  15. Oct 10, 2009 #14

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Re: Prime counting function-- no error.

    That does happen -- sometimes new ideas are more important than being immediately practical (because practical improvements come later). AKS was improved, for' reasonable' numbers (say, 100 digits), over a billionfold since its original publication.

    It's better because e can be chosen to be less than 1.5.
     
  16. Oct 15, 2009 #15
    Re: Prime counting function-- no error.

    The pi(x) counting method is posted at:

    http://www.scribd.com/doc/21131936

    entitled:

    "Upper and Lower Bounds for the Divisor Function"

    I post it there for comments or help with improving it. If someone can help me improve it I will add the name as co-writer.
     
  17. Oct 18, 2009 #16
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prime counting function- no error.
Loading...