Existence of a function for the nth primeby clint222 Tags: factorization, number theory, prime numbers, sieve 

#1
Jan1813, 09:11 AM

P: 36

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 



#2
Jan1813, 11:54 AM

Mentor
P: 10,853

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. 



#3
Jan1813, 04:05 PM

P: 361

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




#4
Jan1913, 07:56 AM

P: 84

Existence of a function for the nth prime
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.




#5
Jan2413, 10:31 AM

P: 7

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 



#6
Jan2413, 11:06 AM

P: 891





#7
Feb1013, 07:14 PM

P: 6

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 


Register to reply 
Related Discussions  
Existence of a two variable function limit  Calculus & Beyond Homework  8  
Proving the nonexistence of a function.  Differential Equations  2  
Existence of a function vs being welldefined?  Calculus  0  
Existence of a certain increasing function  Calculus  2  
Charasteristic prime function...  Linear & Abstract Algebra  12 