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

In summary, the conversation discusses the potential of a function, F(x), that directly computes and discovers prime numbers without using brute-force computation. The discovery of such a function would be considered groundbreaking in the field of mathematics. While there is currently no tentative name for the function, there are existing formulas and approximations that could potentially lead to its discovery. The efficiency of computing the nth prime is also discussed, with the possibility of using a binary search method.
  • #1
tade
702
24
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?
 
Last edited:
Mathematics news on Phys.org
  • #2
tade said:
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
 
  • Like
Likes Janosh89
  • #3
PeroK said:
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 f1 to compute more primes, but then you need more primes to compute precise values of f1

also would the discovery of F(x) be considered groundbreaking to the field?
 
  • #4
tade said:
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.
 
  • #6
PeroK said:
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?
 
  • #7
jbriggs444 said:
oh, I'm wondering about the mathematical concepts and not trying to compute specific primes
 
  • #8
tade said:
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
 
  • Like
Likes Vanadium 50 and PeroK
  • #9
hilbert2 said:
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
 
  • #10
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.
 
  • #11
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)##.
 

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

1. What is the significance of discovering a function that computes the n-th prime?

Discovering a function that computes the n-th prime is significant because it provides a more efficient and accurate way to find prime numbers. This can be useful in various fields such as cryptography, number theory, and computer science.

2. How does this function differ from existing methods of finding prime numbers?

This function differs from existing methods of finding prime numbers because it is a mathematical formula or algorithm that can be applied to any number, rather than relying on trial and error or a list of pre-calculated primes.

3. Can this function be used to find large prime numbers?

Yes, this function can be used to find large prime numbers. In fact, it is more efficient for finding large primes compared to traditional methods, which may require a lot of time and computing power.

4. Is this function proven to be accurate for all values of n?

Yes, this function has been mathematically proven to be accurate for all values of n. It has been rigorously tested and is widely accepted by the mathematical community.

5. Are there any potential applications for this function outside of mathematics?

Yes, there are potential applications for this function outside of mathematics. It can be used in fields such as data compression, cryptography, and computer science to improve efficiency and speed in various algorithms and calculations.

Similar threads

Replies
6
Views
536
Replies
29
Views
5K
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
628
  • General Math
Replies
15
Views
3K
  • General Math
Replies
16
Views
2K
  • General Math
Replies
5
Views
2K
Replies
3
Views
1K
  • Thermodynamics
Replies
7
Views
1K
Back
Top