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

Re: [PrimeNumbers] recursive/iterative definition of prime numbers ?

Expand Messages
  • 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 1 of 2 , Aug 1, 2009
      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
      (unreachable from tomorrow until the 2009-08-20)
    Your message has been successfully submitted and would be delivered to recipients shortly.