RE: [PrimeNumbers] easily computable?
- 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?
From: email@example.com [mailto:firstname.lastname@example.org] On Behalf Of Puff
Sent: Wednesday, March 27, 2013 12:49 AM
Subject: [PrimeNumbers] easily computable?
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: email@example.com
The Prime Pages : http://primes.utm.edu/
Yahoo! Groups Links
- --- In firstname.lastname@example.org,
Chris Caldwell <caldwell@...> wrote:
> There is a fine old article you should read by Herbert WilfMoreover, Herb's article was productive:
> which is "What is an answer?" American Mathematical Monthly,
> 89 (1982), 289-292).
> Added in proof: After reading a preprint of this article,[Here, pi(x) means the number of primes not exceeding x.]
> 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).
gives an idea of his influence.