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

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

Expand Messages
  • Yann Guidon
    hi ! ... and I believe the same as you, ... well, not necessary a formula (I prefer algorithms) and recursivity (as understood in programming) is not
    Message 1 of 2 , Aug 2, 2009
    • 0 Attachment
      hi !

      Gregory J. McClure wrote:
      > Yann,
      >
      > It is my understanding that no formula has ever been found that produces
      > ONLY primes. If that is true,
      and I believe the same as you,

      > then how can one find a formula (I believe in the sense
      > that you are asking) that will find P(n+1) from P(n) recursively?
      well, not necessary a formula (I prefer algorithms)
      and recursivity (as understood in programming) is not necessary,
      it's just that I often mistake recurrence and recursion (sorry).
      (AFAIK certain classes of algorithms can easily be converted
      from iterative to recursive and vice versa).

      Anyway, I concede that I don't use recursivity for this subject.
      I should have written "recurrence", I think. it's the lack of sleep,
      maybe...

      regards,

      > Greg
      yg
    • Gregory J. McClure
      Yann, It is my understanding that no formula has ever been found that produces ONLY primes. If that is true, then how can one find a formula (I believe in the
      Message 2 of 2 , Aug 2, 2009
      • 0 Attachment
        Yann,

        It is my understanding that no formula has ever been found that produces
        ONLY primes.
        If that is true, then how can one find a formula (I believe in the sense
        that you are asking)
        that will find P(n+1) from P(n) recursively?

        Greg


        > 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@ <mailto:primenumbers%40yahoogroups.com> 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)


        .

        <http://geo.yahoo.com/serv?s=97359714/grpId=2607612/grpspId=1705083388/msgId
        =20706/stime=1249197099/nc1=1/nc2=2/nc3=3>




        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.