1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Prime-counting function questions

  1. Aug 2, 2016 #1
    I'm confused about the existence of the prime counting function.

    When I search for information about pi(x), I turn up a lot of information on approximations and algorithms for finding pi(x) but there doesn't seem to be any clear cut formula, yet it seems to exist?
    If there exists formula for the prime counting function, is it that they just aren't very friendly to work with and therefore we resort back to using the approximations? If so, what makes them hard to work with exactly?

    Thank you.
  2. jcsd
  3. Aug 2, 2016 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    The mathematical definition of a "function" doesn't require that function have a formula. It only requires that each x in the domain of the function is mapped to some unique y in the co-domain. To show a function exists, you only have to show that some procedure exists for finding y once x is given. The procedure for the prime counting function is "List all the prime numbers that are less than equal to x and count how many numbers are in the list".

    People interested in mathematics are interested in functions that do have formulas of the usual type. It would be nice to discover such a formula for the prime counting function, but (as far as I know) all that is currently available are approximations.

    People who study computer science, study algorithms and often these are functions that can't be implemented as straightforward formulas. For example, a computer could be programmed to compute the prime counting function. The program wouldn't be a simple one-line formula. There would be a lot of steps to the program.
  4. Aug 3, 2016 #3
    Figures I was being sloppy, a function is just a ordered pair(with some rules). The 2nd paragraph answers the question.

    Helpful post, I appreciate it, thank you.
  5. Aug 3, 2016 #4
    I don't know what you call clear cut, but i found two formulas that look prety clear to me:
    from http://mathworld.wolfram.com/PrimeCountingFunction.html, and
    from http://mathworld.wolfram.com/RiemannPrimeCountingFunction.html. ##f## and ##\mu## are defined in the webpage.

    The second formula is more algorithmic, if you look at the definitions. But the first formula is also computationally intensive. The choice of algorithm certainly matters for the computer scientist, and algorithms that lead to approximate solutions are fine too because the computed values should be close to an integer, so they can be rounded to get the correct value, which we know is an integer.

    But perhaps the better reason to use approximations, is that for large ##n##, the exact algorithms are extremely inefficient, in particular the first formula (Hardy and Wright, 1979). Just you try computing ##\pi(100)## and you will see what I mean.

    What you really want is a easy formula to compute the prime counting function, but what you really should ask for is the best algorithm for computing it. To make this point clear we consider the function ##f(x)=x^2+3x##. The formula I have given actually prescribes a great algorithm to compute the values of the function. It just happens that in this case, the computational power you need is very small, compared to ##\pi(x)##. I'm just highlighting the obvious but overlooked fact that how hard it is to compute values for functions depends on the algorithm you use, and on the functions themselves.
    Last edited: Aug 3, 2016
  6. Aug 3, 2016 #5
    Hey Lucas SV, you're right I do mean easy to compute. I overlooked the first which is pretty "clear cut" but as you have said, it's useless because of how large factorials get.

    Appreciate the insight, thank you.
  7. Aug 3, 2016 #6


    User Avatar
    Science Advisor

    Try using an approximate solution to compute pi(x) - pi(x-1).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted