My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree15Thanks
Reply
 
LinkBack Thread Tools Display Modes
August 14th, 2017, 12:34 PM   #11
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

Quote:
Originally Posted by JeffM1 View Post
I suspect the question is whether there is a simpler pattern to the primes than a list of the primes themselves and whether that pattern can be expressed in a formula.
There exists a closed-form expression that generates the primes and only the primes. See the checked answer and its comments here, along with the comment by André Nicolas (author of the checked comment) to the unchecked comment below it.

https://math.stackexchange.com/quest...form-can-exist

Here's the comment:

Quote:
There is an elementary function that generates all primes, and only the primes. It can be built out of addition, subtraction, multiplication, and absolute value. This is a straightforward consequence of the result of Matijasevic that for any recursively enumerable set S of positive integers, there is a polynomial P(x1,…,xn) with integer coefficients such that the range of P is the elements of S, together with some negative numbers. The negative values can be replaced by (say) 2 by using some tricks with the absolute value function.
ps -- Also see the first formula here ... https://en.wikipedia.org/wiki/Formul...on.27s_theorem

That's a closed-form expression for the n-th prime. That page also contains a number of other closed-form expressions of interest to the discussion.

Bottom line there are formulas for primes. They are generally not any more computationally efficient than brute-force sieving, which is why they're not more famous.
Thanks from Benit13 and JeffM1

Last edited by Maschke; August 14th, 2017 at 12:44 PM.
Maschke is online now  
 
August 14th, 2017, 01:38 PM   #12
Senior Member
 
Joined: May 2016
From: USA

Posts: 826
Thanks: 335

Thanks Maschke for putting me straight on closed form formulas for primes. I was just wrong.

I still am not convinced that we have any clear idea what the original questions means.
JeffM1 is offline  
August 14th, 2017, 04:44 PM   #13
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

Quote:
Originally Posted by JeffM1 View Post
Thanks Maschke for putting me straight on closed form formulas for primes. I was just wrong.
Glad to help. I just Googled around. It was news to me too. I don't actually follow all the bits about Diophantine systems and how many variables you need and such. Add to list of things I'll never know about.

Quote:
Originally Posted by JeffM1 View Post
I still am not convinced that we have any clear idea what the original questions means.
I think you can ask if the distribution of primes is statistically random in some sense. I believe this is related to the Riemann hypothesis so it's a pretty deep question.
Maschke is online now  
August 14th, 2017, 07:42 PM   #14
Senior Member
 
Joined: Feb 2016
From: Australia

Posts: 1,422
Thanks: 484

Math Focus: Yet to find out.
Quote:
Originally Posted by Maschke View Post
It's deterministic. Someone complained that it's not efficiently computable. That's irrelevant. It's computable.
I'm a bit confused about this. If a closed form exists, and computational efficiency is irrelevant, what's all the hullabaloo about primes? I guess what I don't understand is: what don't we know about primes?..Embarrassingly, I didn't even know about this closed form until now.
Joppy is online now  
August 15th, 2017, 12:12 AM   #15
Global Moderator
 
Joined: Dec 2006

Posts: 18,166
Thanks: 1424

Quote:
Originally Posted by Maschke View Post
That's a closed-form expression for the n-th prime.
How so?
skipjack is offline  
August 15th, 2017, 09:12 AM   #16
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

Quote:
Originally Posted by Joppy View Post
I'm a bit confused about this. If a closed form exists, and computational efficiency is irrelevant, what's all the hullabaloo about primes? I guess what I don't understand is: what don't we know about primes?..Embarrassingly, I didn't even know about this closed form until now.
Not sure I understand the question. People have cared about primes since Euclid. Computational efficiency goes back to around the 1880's I think.


Quote:
Originally Posted by skipjack View Post
How so?
Explanation's on the Wiki page I linked. I didn't work through the details. It uses the floor function. Whether that's within someone's def of closed form is subjective, since there is no official def of closed form.

Last edited by Maschke; August 15th, 2017 at 09:16 AM.
Maschke is online now  
August 15th, 2017, 09:31 AM   #17
Global Moderator
 
Joined: Dec 2006

Posts: 18,166
Thanks: 1424

It generates the primes. That's not the same thing as generating the n-th prime.
Thanks from Joppy
skipjack is offline  
August 15th, 2017, 02:52 PM   #18
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,042
Thanks: 2344

Math Focus: Mainly analysis and algebra
Quote:
Originally Posted by skipjack View Post
It generates the primes. That's not the same thing as generating the n-th prime.
More to the point, that function generates $n+1$ if it's prime and $2$ otherwise. So it is more or less useless as a function.
v8archie is offline  
August 15th, 2017, 04:16 PM   #19
Senior Member
 
Joined: Oct 2009

Posts: 142
Thanks: 60

Quote:
Originally Posted by v8archie View Post
More to the point, that function generates $n+1$ if it's prime and $2$ otherwise. So it is more or less useless as a function.
Then what would be a useful function? What do we define by a useful, efficient function? Without such an answer, this thread is pretty much meaningless.
Micrm@ss is offline  
August 15th, 2017, 06:19 PM   #20
Senior Member
 
Joined: Aug 2012

Posts: 1,641
Thanks: 415

Quote:
Originally Posted by v8archie View Post
More to the point, that function generates $n+1$ if it's prime and $2$ otherwise. So it is more or less useless as a function.
That's a consequence of Wilson's theorem. It's a perfect prime recognizer. A number $n$ is prime if and only if $(n-1)! \equiv -1 \pmod n$.

At first glance it's impressive, here's a perfect primality test. But by the time we calculate $(n-1)!$ we might as well just use brute force trial divisors to determine if $n$ is prime. There's much less here than meets the eye.

Even so, you can use Wilson's theorem to cook up a "closed form" expression that cranks out primes, even if it throws an error (outputs 2) on non-primes. You can think of it as a partial function, which is a function defined on some proper subset of its domain. I agree it's not a total function, but is that a core objection?

"Closed form" doesn't have an official definition, it's more like we know one when we see one. And not everyone agrees.

But if you require a closed form to be "useful" as well as to just exist, then you have to say what that is. It seems like an additional requirement.

By the way it turns out that there is a better way than trial divisors to determine if a number is prime. In 2006 someone showed that there is a polynomial time algorithm to determine if an arbitrary number is prime. This is a fantastic result, so counterintuitive.

https://en.wikipedia.org/wiki/AKS_primality_test

Last edited by Maschke; August 15th, 2017 at 06:34 PM.
Maschke is online now  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
primes, proof, random



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Elementary proof of the 1D simple random walk "infinite crossing" theorem Bromster Algebra 0 December 24th, 2015 11:09 PM
how "random" are online "random" spinners? skynet Probability and Statistics 1 June 18th, 2014 01:26 PM
A "simple" application of dirac delta "shift theorem"...help SedaKhold Calculus 0 February 13th, 2012 12:45 PM
"recurrent" mersenne primes brunojo Number Theory 70 June 15th, 2009 05:37 PM





Copyright © 2017 My Math Forum. All rights reserved.