Browse Groups

• ## RE: [PrimeNumbers] easily computable?

(4)
• NextPrevious
• There is a fine old article you should read by Herbert Wilf which is ``What is an answer? American Mathematical Monthly, 89 (1982), 289-292). He presents a
Message 1 of 4 , Mar 27
View Source
There is a fine old article you should read by Herbert Wilf which is ``What is an answer?" American Mathematical Monthly, 89 (1982), 289-292). He presents a number of formulas for the primes (and for subsets of the primes; and which only produce primes; and ... the question can be stated in many ways).

I do not think "easily computable" is well defined, but it is easily recognized. Primes are obviously easily computable (consider the discussion of how many million can be found per second using various sieves). I am not sure asymptotic complexity measurements help as there is a polynomial bounded test for primality, but numbers of any size, it is currently unusable. Tougher is the question "what is a formula?" (as many formulas I have seen for the primes are sieves in disguise). They are amusing.

I suspect by "easily computable" they actually mean "useful for computing primes." And we would know if there was a useful formula know, because folks would use it, what other definition would you need?

-----Original Message-----
Sent: Wednesday, March 27, 2013 12:49 AM

The wiki page on Formula for primes, says:

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is easily computable is presently known. A number of constraints are known: what such a "formula" can and cannot be.

What does easily computable mean exactly? Google was no help.
I emailed the American Mathematical Society with this question, and no response yet.

------------------------------------

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://primes.utm.edu/

• ... [Here, pi(x) means the number of primes not exceeding x.] http://www.math.upenn.edu/History/obits/Herb_Wilf.html gives an idea of his influence. David
Message 1 of 4 , Mar 27
View Source
Chris Caldwell <caldwell@...> wrote:

> There is a fine old article you should read by Herbert Wilf
> which is "What is an answer?" American Mathematical Monthly,
> 89 (1982), 289-292).

Moreover, Herb's article was productive:

> Jeffrey Lagarias and Andrew Odlyzko of Bell Laboratories
> found an algorithm that computes pi(x) in time
> O(x^(3/5+eps)): a true "formula" for pi(x).

[Here, pi(x) means the number of primes not exceeding x.]

http://www.math.upenn.edu/History/obits/Herb_Wilf.html
gives an idea of his influence.

David
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.