Expand Messages
• What is the definition of a formula? Input x = Output y Prime[x] = y Probably to have a function like Prime right now, would require to calculate its
Message 1 of 4 , Mar 26, 2013
• 0 Attachment
What is the definition of a formula?

Input 'x' => Output 'y'

Prime[x] => y

Probably to have a function like 'Prime' right now, would require to
calculate its modular exponentiation with all primes less than it.

Imagine that Prime[i] = *257885161 - 1

*Do we know 'i' ? So till we don't know the exact value of 'i' we'll have a
broken definition for Prime function ...
**
On Wed, Mar 27, 2013 at 10:18 AM, Puff <puffone@...> wrote:

> **
>
>
> 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.
>
>
>

--
"Mathematics is the queen of the sciences and number theory is the queen of
mathematics."
--Gauss

[Non-text portions of this message have been removed]
• 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 2 of 4 , Mar 27, 2013
• 0 Attachment
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 3 of 4 , Mar 27, 2013
• 0 Attachment
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.