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

1. recursive definition of prime numbers ?

Expand Messages
  • Kermit Rose
    ... The sieve program for finding primes is a recursively or iteratively definition of primes. Very simply, p(n+1) is the next integer after p(n) that is not
    Message 1 of 2 , Aug 1 6:16 PM
    • 0 Attachment
      primenumbers@yahoogroups.com wrote:
      > There is 1 message in this issue.
      >
      > Topics in this digest:
      >
      > 1. recursive definition of prime numbers ?
      > From: Yann GUIDON
      >
      >
      > Message
      > ________________________________________________________________________
      > 1. recursive definition of prime numbers ?
      > Posted by: "Yann GUIDON" whygee@... yasep16
      > Date: Fri Jul 31, 2009 10:28 am ((PDT))
      >
      > Hello,
      >
      > I'm digging the subject of how primes can be defined,
      > recursively or iteratively. All Google shows me is
      > "recursive prime numbers", not what I want.
      > I know the classic definitions but wonder if anyone
      > has ever been able to define P(n+1) from the value(s)
      > of P(n) (and eventually any prime down to 2).
      >
      > yg
      >

      The sieve program for finding primes is a recursively or iteratively
      definition of primes.

      Very simply,

      p(n+1) is the next integer after p(n) that is not divisible by any of
      p1,p2,p3,p4,.... pn.

      Of course improvements on this basic definition can be made.

      We can stop testing as soon as we reach the smallest prime whose square
      exceeds pn.

      The most efficient way to make these tests is of course by either the
      classical prime number sieve, or by the more efficient modern variations.

      Kermit Rose
    • Yann Guidon
      Hello and thank you for your answer, even if it s not what I expected, since it falls in the classic definitions bucket that I try to escape from. but
      Message 2 of 2 , Aug 1 11:46 PM
      • 0 Attachment
        Hello and thank you for your answer, even if it's not what I expected,
        since it falls in the "classic" definitions bucket that I try to escape from.
        but anyway...

        Kermit Rose wrote:
        > primenumbers@yahoogroups.com wrote:
        >> recursive definition of prime numbers ?
        >>
        >> Hello,
        >>
        >> I'm digging the subject of how primes can be defined,
        >> recursively or iteratively. All Google shows me is
        >> "recursive prime numbers", not what I want.
        >> I know the classic definitions but wonder if anyone
        >> has ever been able to define P(n+1) from the value(s)
        >> of P(n) (and eventually any prime down to 2).
        >>
        >> yg
        >
        > The sieve program for finding primes is a recursively or iteratively
        > definition of primes.
        >
        > Very simply,
        >
        > p(n+1) is the next integer after p(n) that is not divisible by any of
        > p1,p2,p3,p4,.... pn.
        > Of course improvements on this basic definition can be made.

        sure but one has to find "p(n) that is not divisible by any of" the precedent primes,
        which requires further nested iteration loops with divides/remainders etc...
        I'm more interested by algos that tell me for sure that "the following prime is x"
        instead of "let's see if the following number is prime"...

        > We can stop testing as soon as we reach the smallest prime whose square exceeds pn.
        > The most efficient way to make these tests is of course by either the
        > classical prime number sieve, or by the more efficient modern variations.

        The issue that I have with these methods is that they don't give me any information
        of the kind that I need. They just say "this number is not a prime" with little hint
        about why or how... As if one needs an "oracle" (in the cryptography sense) to
        know that n is in /P/. I want to get rid of this oracle (that can take many forms).

        I seem to have found an answer to my questions but it looks so "not difficult" that
        my first reaction was to doubt about my method. I've worked very hard and asked other
        people to see where I could be wrong, with no success.
        Now my question is "am I the first to think about this, or is everybody overlooking
        a few details that seem obvious to me ?"
        So I am probing the wisdom and knowledge of the group.

        Here is my rephrased question :
        Does someone know an algo that gives the next prime p(i+1) from the value of p(i)
        - without trials or "scan until the next satisfying answer"
        - without division/multiplies/sqrt/remainder (that is : the "oracle")
        - without doubt (not a statistical method)
        - without encoded or hidden constants (I can start with only "1")
        - some auxiliary and generated data are allowed though :-)
        Pritchard's work on the wheel sieves is almost there but it's not satisfying
        because it's still too "classical" (in the sense that it's just another form
        of sieve, so it does not tell me "why" things are as they are, just "how"...)

        Best regards,
        > Kermit Rose
        YG
        (unreachable from tomorrow until the 2009-08-20)
      Your message has been successfully submitted and would be delivered to recipients shortly.