My Math Forum Proof Primes are not "random"
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

August 14th, 2017, 11:34 AM   #11
Senior Member

Joined: Aug 2012

Posts: 1,529
Thanks: 364

Quote:
 Originally Posted by JeffM1 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.

Last edited by Maschke; August 14th, 2017 at 11:44 AM.

 August 14th, 2017, 12:38 PM #12 Senior Member   Joined: May 2016 From: USA Posts: 785 Thanks: 312 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.
August 14th, 2017, 03:44 PM   #13
Senior Member

Joined: Aug 2012

Posts: 1,529
Thanks: 364

Quote:
 Originally Posted by JeffM1 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 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.

August 14th, 2017, 06:42 PM   #14
Senior Member

Joined: Feb 2016
From: Australia

Posts: 1,322
Thanks: 453

Math Focus: Yet to find out.
Quote:
 Originally Posted by Maschke 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.

August 14th, 2017, 11:12 PM   #15
Global Moderator

Joined: Dec 2006

Posts: 17,919
Thanks: 1386

Quote:
 Originally Posted by Maschke That's a closed-form expression for the n-th prime.
How so?

August 15th, 2017, 08:12 AM   #16
Senior Member

Joined: Aug 2012

Posts: 1,529
Thanks: 364

Quote:
 Originally Posted by Joppy 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 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 08:16 AM.

 August 15th, 2017, 08:31 AM #17 Global Moderator   Joined: Dec 2006 Posts: 17,919 Thanks: 1386 It generates the primes. That's not the same thing as generating the n-th prime. Thanks from Joppy
August 15th, 2017, 01:52 PM   #18
Math Team

Joined: Dec 2013
From: Colombia

Posts: 6,943
Thanks: 2268

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by skipjack 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.

August 15th, 2017, 03:16 PM   #19
Senior Member

Joined: Oct 2009

Posts: 141
Thanks: 59

Quote:
 Originally Posted by v8archie 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.

August 15th, 2017, 05:19 PM   #20
Senior Member

Joined: Aug 2012

Posts: 1,529
Thanks: 364

Quote:
 Originally Posted by v8archie 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 05:34 PM.

 Tags primes, proof, random

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Bromster Algebra 0 December 24th, 2015 10:09 PM skynet Probability and Statistics 1 June 18th, 2014 12:26 PM SedaKhold Calculus 0 February 13th, 2012 11:45 AM brunojo Number Theory 70 June 15th, 2009 04:37 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top