Existence of a function for the n-th prime

clint222

Hello!

This question may seem silly. I'm a first year engineering and computer science student, not a mathematics student. I have only recently become interested in prime numbers, factorization algorithms, and prime number finding algorithms. I know only extremely elementary number theory, so forgive my ignorance.

I understand the idea behind the Sieve of Eratosthenes, and I realize that there are a variety of similar but more efficient, based on the same general idea.

I had been interested in the idea that a function for the nth prime exists. That is, a function which could be used to directly all of the prime numbers. For example, something of the form p(n), where p(1) = 2, p(2) = 3, etc. I mean one that doesn’t require knowing all of the primes before n, like integer sieves require.

A number theory textbook I have says that no such function has ever been found, and it is likely impossible for such a function to exist. It does discuss some recursive functions that can calculate the nth prime, but they are actually quite a bit less efficient to find prime numbers than a simple integer sieve.

I was wondering if there is any reason why a more efficient prime finding function is thought to be impossible. Or is it simply that evidence of such a thing hasn't been found so it probably isn't possible? I know that this type of function has been of interest for a very long time.

Thanks for helping me learn more about number theory!

Clint

mfb

Well, there is a function: Let p map from the natural numbers to the natural numbers, and let p(n) be defined as the nth prime. There it is.
The problem is: We have no idea how to calculate p(n) efficiently. And as all attempts so far failed - even for weaker requirements* - it might be impossible to find an efficient way to calculate it. In general, prime numbers do not follow any nice patterns.

*like a function p'(n) which just gives some primes in ascending order, not all. Even that would be a surprise.

Petek

You might be interested in reading the Wikipedia article titled Formulas for Primes.

epsi00

has not been found does not necessarily mean does not exist. I suggest you try to come up with a formula and see what kind of problem you run into.

Jack Jenkins

There is a function [itex]\pi[/itex](x) that takes the natural numbers as its input and outputs the number of primes less than or equal to x.

There are some nice properties of this function. For instance, the growth rate as x approaches infinity approaches x/lnx

ramsey2879

Unless [itex]\pi[/itex](x) is viewed as an approximation only, there is no simple way known to calculate it, just as there is no known way to simply output the nth prime, given n.

LioNiNoiL

Chris Caldwell lists the Wilans function for ##p_n## at the bottom of the page at:
http://primes.utm.edu/notes/faq/p_n.html