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

Explicit calculation of prime positive integers

Expand Messages
  • Kermit Rose
    Kermit says: Hello Yann. Yann says: 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
    Message 1 of 2 , Aug 2, 2009
    • 0 Attachment
      Kermit says:
      Hello Yann.

      Yann says:

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

      Kermit says:
      One could construct the following vector sequence that would make clear
      what it is that makes a prime a prime.

      To make the next entry,
      Just add 1 to each number in the vector.

      Each time you cross a prime, you add another entry for that prime.

      Each time you reach 2 in the 2's place, start over, so that the next
      entry in the 2's place is a 1.
      Each time you reach 3 in the 3's place, start over so that the next
      entry in the 3's place is a 1.
      etc

      2 = [2] First prime.
      3 = [1] Prime because 2 is not in the 2's place.
      4 = [2,1] Not prime because in the 2's place is a 2.
      5 = [1,2] Prime because in the 2's place is not a 2, and in the 3's
      place is not a 3.
      6 = [2,3,1] Not prime because in the 2's place is a 2. Also not prime
      because in the 3's place is a 3.
      7 = [1,1,2] Prime because in the 2's place is not a 2, and in the 3's
      place is not a 3, and in the 5's place is not a 5.
      8 = [2,2,3,1] Not prime because in the 2's place is a 2.
      9 = [1,3,4,2] Not prime because in the 3's place is a 3.
      10 = [2,1,5,3] Not prime because in the 2's place is a 2, and also
      because in the 5's place is a 5.
      11 = [1,2,1,4] Prime because 2 is not in the 2's place, and 3 is not in
      the 3's place, and 5 is not in the 5's place, and 7 is not in the 7's place.
      12 = [2,3,2,5,1] Not prime because 2 is in the 2's place, and also
      because 3 is in the 3's place.
      13 = [1,1,3,6,2] Prime because no previous prime is in its place.
      14 = [2,2,4,7,3,1] Not prime because 2 is in the 2's place, and also
      because 7 is in the 7's place
      15 = [1,3,5,1,4,2] Not prime because 3 is in the 3's place, and also
      because 5 is in the 5's place.
      16 = [ 2,1,1,2,5,3] Not prime because 2 is in the 2's place.
      17 = [1,2,2,3,6,4] Prime because no previous prime is in its place.
      18 = [2,3,3,4,7,5,1] Not prime because 2 is in the 2's place, and also
      because 3 is in the 3's place.
      19 = [1,1,4,5,8,6,2] Prime because no previous prime is in its place.
      20 = [2,2,5,6,9,7,3,1] Not prime because 2 is in the 2's place, and
      also because 5 is in the 5's place.
      21 = [1,3,1,7,10,8,4,2] Not prime because 3 is in the 3's place and
      also because 7 is in the 7's place.
      22 = [2,1,2,1,11,9,5,3] Not prime because 2 is in the 2's place, and
      also because 11 is in the 11's place.
      23 = [1,2,3,2,1,10,6,4] Prime because no previous prime is in its place.
      24 = [2,3,4,3,2,11,7,5] Not prime because 2 is in the 2's place, and
      also because 3 is in the 3's place.
      25 = [1,1,5,4,3,12,8,6] Not prime because 5 is in the 5's place.
      etc

      Yann says:

      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.


      Kermit says:
      Yann, in order to answer your question, we need to know details of your
      method.


      Yann says:

      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"...)

      Kermit says:
      Hmmmm...... Why versus how.

      I think that maybe I have never understood the meaning of "why?".

      For me, answering how things happen does answer all my questions.

      I myself see no difference in meaning for "why?" and "how?".


      Kermit Rose
    • Yann Guidon
      Hi ! ... hmmmm it looks like... some sort of folded sieve, it reminds me of stack-based algorithms, and your vector is a bit like a stack... quite clever :-) a
      Message 2 of 2 , Aug 2, 2009
      • 0 Attachment
        Hi !

        Kermit Rose wrote:
        > Kermit says:
        > One could construct the following vector sequence that would make clear
        > what it is that makes a prime a prime.
        >
        > To make the next entry,
        > Just add 1 to each number in the vector.
        >
        > Each time you cross a prime, you add another entry for that prime.
        >
        > Each time you reach 2 in the 2's place, start over, so that the next
        > entry in the 2's place is a 1.
        > Each time you reach 3 in the 3's place, start over so that the next
        > entry in the 3's place is a 1.
        > etc
        hmmmm it looks like... some sort of folded sieve,
        it reminds me of stack-based algorithms,
        and your vector is a bit like a stack... quite clever :-)
        a stack of counter in fact...
        but this method needs to scan all numbers.
        it does not jump from one prime number to the other :-/

        > 2 = [2] First prime.
        > 3 = [1] Prime because 2 is not in the 2's place.
        > 4 = [2,1] Not prime because in the 2's place is a 2.
        > 5 = [1,2] Prime because in the 2's place is not a 2, and in the 3's
        > place is not a 3.
        > 6 = [2,3,1] Not prime because in the 2's place is a 2. Also not prime
        > because in the 3's place is a 3.
        > 7 = [1,1,2] Prime because in the 2's place is not a 2, and in the 3's
        > place is not a 3, and in the 5's place is not a 5.
        <snip>
        > etc
        I'll think carefully about the method you show.
        does it have a name, where is it used, how can it be found or referenced ?

        > Kermit says:
        > Yann, in order to answer your question, we need to know details of your
        > method.
        I have just put some example code online at http://ygdes.com/sources/premiers.html
        The algo is in JavaScript inside the page (very handy).
        I'm not (yet ?) used to the tools that many contributors here use
        (pari ?), it could change when I get a better idea about it.

        The algorithm is explained in an article that will soon be published.
        The original is there : http://ygdes.com/sources/misc-prems.html
        (sorry, french only). It's a newcomer-level article but some
        interesting stuff is at the end.

        > Kermit says:
        > Hmmmm...... Why versus how.
        > I think that maybe I have never understood the meaning of "why?".
        > For me, answering how things happen does answer all my questions.
        > I myself see no difference in meaning for "why?" and "how?".
        maybe my "why" is the "how" of the "how" ?

        anyway i'm too tired to dissert about it now.

        thank you very much for your insight,
        > Kermit Rose
        yg
      Your message has been successfully submitted and would be delivered to recipients shortly.