Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] easily computable?

Expand Messages
  • Mohsen Afshin
    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]
    • Chris Caldwell
      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-----
        From: primenumbers@yahoogroups.com [mailto:primenumbers@yahoogroups.com] On Behalf Of Puff
        Sent: Wednesday, March 27, 2013 12:49 AM
        To: primenumbers@yahoogroups.com
        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: primenumbers-unsubscribe@yahoogroups.com
        The Prime Pages : http://primes.utm.edu/

        Yahoo! Groups Links
      • djbroadhurst
        ... [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
          --- In primenumbers@yahoogroups.com,
          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:

          > Added in proof: After reading a preprint of this article,
          > 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.