I Prime-counting function questions

[AdamsJoK]

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.

 

[Stephen Tashi]

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?

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.

 

[AdamsJoK]

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.

 

[Lucas SV]

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.

 

[AdamsJoK]

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.

 

[jbriggs444]

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

Try using an approximate solution to compute pi(x) - pi(x-1).