August 14th, 2017, 11:34 AM  #11  
Senior Member Joined: Aug 2012 Posts: 1,971 Thanks: 550  Quote:
https://math.stackexchange.com/quest...formcanexist Here's the comment: Quote:
That's a closedform expression for the nth prime. That page also contains a number of other closedform expressions of interest to the discussion. Bottom line there are formulas for primes. They are generally not any more computationally efficient than bruteforce 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: 1,084 Thanks: 446 
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,971 Thanks: 550  Quote:
Quote:
 
August 14th, 2017, 06:42 PM  #14 
Senior Member Joined: Feb 2016 From: Australia Posts: 1,610 Thanks: 550 Math Focus: Yet to find out.  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: 19,287 Thanks: 1681  
August 15th, 2017, 08:12 AM  #16  
Senior Member Joined: Aug 2012 Posts: 1,971 Thanks: 550  Quote:
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: 19,287 Thanks: 1681 
It generates the primes. That's not the same thing as generating the nth prime.

August 15th, 2017, 01:52 PM  #18 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,342 Thanks: 2465 Math Focus: Mainly analysis and algebra  
August 15th, 2017, 03:16 PM  #19 
Senior Member Joined: Oct 2009 Posts: 436 Thanks: 147  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,971 Thanks: 550  Quote:
At first glance it's impressive, here's a perfect primality test. But by the time we calculate $(n1)!$ 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 nonprimes. 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  

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 10:09 PM 
how "random" are online "random" spinners?  skynet  Probability and Statistics  1  June 18th, 2014 12:26 PM 
A "simple" application of dirac delta "shift theorem"...help  SedaKhold  Calculus  0  February 13th, 2012 11:45 AM 
"recurrent" mersenne primes  brunojo  Number Theory  70  June 15th, 2009 04:37 PM 