Significance of discovering a function which computes the n-th prime?

[tade]

Let's say the function is of a form F(x), where F(n) gives us the value of the n-th prime number, for all values of n.

And it computes and discovers subsequent prime numbers directly without using any form of brute-force computation.If such a function is discovered, how ground-breaking would it be considered to the field of mathematics?

Also, even though it has not been discovered, does this F(x) function have a tentative name?

 

[PeroK]

Let's say the function is of a form F(x), where F(n) gives us the value of the n-th prime number, for all values of n.
And it computes and discovers subsequent prime numbers directly without using any form of brute-force computation.

If such a function is discovered, how ground-breaking would it be considered to the field of mathematics?

Also, even though it has not been discovered, does this F(x) function have a tentative name?

The function exists, of course, but it's how efficently you can compute $f(n)$ that is the question. There's a little something about it here:

https://en.wikipedia.org/wiki/Formula_for_primes#A_function_that_represents_all_primes

 

[tade]

The function exists, of course, but it's how efficently you can compute $f(n)$ that is the question. There's a little something about it here:

https://en.wikipedia.org/wiki/Formula_for_primes#A_function_that_represents_all_primes

It's a "Catch-22 formula" isn't it?

You need precise values of f₁ to compute more primes, but then you need more primes to compute precise values of f₁

also would the discovery of F(x) be considered groundbreaking to the field?

 

[PeroK]

also would the discovery of F(x) be considered groundbreaking to the field?

The ability to compute the nth prime relatively quickly would be something very special.

 

[jbriggs444]

You could visit https://primes.utm.edu/nthprime/

 

[tade]

The ability to compute the nth prime relatively quickly would be something very special.

Like a general form of Euler's "lucky" polynomials right? is there a tentative name for such a function?

 

[tade]

You could visit https://primes.utm.edu/nthprime/

oh, I'm wondering about the mathematical concepts and not trying to compute specific primes

 

[hilbert2]

And it computes and discovers subsequent prime numbers directly without using any form of brute-force computation.

There's no clear-cut difference between what's "brute-force" and "non-brute-force" computation. Defining a function by just saying that it's the next number produced by the sieve of Eratosthenes is just as valid as defining it as a polynomial.

There are ways to define polynomials of many integer variables such that all their positive values are primes, but this doesn't have much use in practical computation:

https://primes.utm.edu/glossary/page.php?sort=MatijasevicPoly

 

[tade]

There's no clear-cut difference between what's "brute-force" and "non-brute-force" computation. Defining a function by just saying that it's the next number produced by the sieve of Eratosthenes is just as valid as defining it as a polynomial.

There are ways to define polynomials of many integer variables such that all their positive values are primes, but this doesn't have much use in practical computation:

https://primes.utm.edu/glossary/page.php?sort=MatijasevicPoly

I think the difference is that with a brute-force method we're unsure of how many steps it will take to arrive at the answer.

by the way Willans' formula is just an approximation of the prime-counting function π(n) right?

https://www.theoremoftheday.org/NumberTheory/Willans/TotDWillans.pdf

 

[mfb]

With trial division you know how many steps you need to test a given prime, and you know that a given prime is at most twice the previous prime. That means even the most stupid approach to find the next prime has an upper limit on the amount of computation. The upper limit is just way too high to be useful. And it's considered to be brute force.

Willans' formula should be exact, it is basically a primality check for every number (and slower than most other primality checks). See the explanation on the right hand side.

 

[suremarc]

Calculating $p_n$ is not much harder than calculating $\pi(x)$, according to this stackexchange post. A simple method would be to obtain bounds $a_n<p_n<b_n$, then do a binary search on $\pi(x)$ in that neighborhood. You would have to do at most $\lfloor\log_2(b_n-a_n)+1\rfloor$ computations of $\pi(x)$.