Register to reply

Existence of a function for the n-th prime

Share this thread:
clint222
#1
Jan18-13, 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
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
mfb
#2
Jan18-13, 11:54 AM
Mentor
P: 11,925
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
#3
Jan18-13, 04:05 PM
Petek's Avatar
P: 361
You might be interested in reading the Wikipedia article titled Formulas for Primes.

epsi00
#4
Jan19-13, 07:56 AM
P: 84
Existence of a function for the n-th 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.
Jack Jenkins
#5
Jan24-13, 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
ramsey2879
#6
Jan24-13, 11:06 AM
P: 894
Quote Quote by Jack Jenkins View Post
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
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
#7
Feb10-13, 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 non-existence of a function. Differential Equations 2
Existence of a function vs being well-defined? Calculus 0
Existence of a certain increasing function Calculus 2
Charasteristic prime function... Linear & Abstract Algebra 12