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

Benefits of sieving. References please

Expand Messages
  • garychaffey2
    Could somebody please give me some online references to information about the benefits of sieving. E.g. Suppose a number K is a random integer then it has a 1
    Message 1 of 4 , Jul 12, 2005
    • 0 Attachment
      Could somebody please give me some online references to information
      about the benefits of sieving.
      E.g. Suppose a number K is a random integer then it has a 1 in 1/ln K
      chance of being prime but if K is not divisible by 2 or 3 then the
      chance of it being prime is 2/(3lnK)
      etc
      That type of thing.
      Thanks in advance
      Gary
    • Gary Chaffey
      As usual a typo on my formula! I know it was just an example but if K is not divisible by 2 or 3 then the chance of it being prime is 3/(lnK) Gary garychaffey2
      Message 2 of 4 , Jul 12, 2005
      • 0 Attachment
        As usual a typo on my formula!
        I know it was just an example but if K is not divisible by 2 or 3 then the
        chance of it being prime is 3/(lnK)
        Gary
        garychaffey2 <garychaffey2@...> wrote:
        Could somebody please give me some online references to information
        about the benefits of sieving.
        E.g. Suppose a number K is a random integer then it has a 1 in 1/ln K
        chance of being prime but if K is not divisible by 2 or 3 then the
        chance of it being prime is 2/(3lnK)
        etc
        That type of thing.
        Thanks in advance
        Gary




        Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
        The Prime Pages : http://www.primepages.org/





        ---------------------------------
        YAHOO! GROUPS LINKS


        Visit your group "primenumbers" on the web.

        To unsubscribe from this group, send an email to:
        primenumbers-unsubscribe@yahoogroups.com

        Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.


        ---------------------------------




        ---------------------------------
        Yahoo! Messenger NEW - crystal clear PC to PCcalling worldwide with voicemail

        [Non-text portions of this message have been removed]
      • Sarad AV
        hi, The following observation might help. From 1-10, the numbers not divisible by 2,3 are 1,5,7. I.e 3 in number. Between 11-20,the numbers not divisible by
        Message 3 of 4 , Jul 12, 2005
        • 0 Attachment
          hi,

          The following observation might help.

          From 1-10, the numbers not divisible by 2,3 are 1,5,7.
          I.e 3 in number.

          Between 11-20,the numbers not divisible by 2,3 are
          11,13,17,19.
          I.e 4 in number.

          Between 21-30,the numbers not divisible by 2,3 are
          23,25,29.
          I.e 3 in number.

          So, between any 10 consecutive numbers of the form xx1
          and xx0.

          Either of the 3 cases occur.
          3 | xx1 and so 3| xx1,xx4,xx7.(Case 1)
          3 | xx1+1 and so 3| xx2,xx5,xx8.(Case 2)
          3 | xx1+2 and so 3| xx3,xx6,xx9.(Case 3)

          The favourable condition in Case 1 is the occurance of
          xx1 and xx7 because 2|xx4 anyway. So, the number of
          favourable case is 2.

          The favourable condition in Case 2 is the occurance of
          xx5 because 2|xx2 and 2|xx8 anyway. So, the number of
          favourable case is 1.

          The favourable condition in Case 3 is the occurance of
          xx3 and xx9 because 2|xx6 anyway. So, the number of
          favourable case is 2.

          Between any 10 consecutive numbers xx1 and xx0, all
          the time 3 divides (2 of the numbers) or (one of the
          numbers) in accordance to the favourable cases in Case
          1,2 and 3.

          Since 5 of the numbers between 10 consecutive numbers
          xx1 and xx0 is divisibe by 2, the total of numbers
          divisible by 2 and 3 is

          Case 1: 5+2=7
          Case 2: 5+1=6
          Case 3: 5+2=7.

          Therefore 6 out of every 10 or 7 out of every 10
          consecutive numbers is divisible by 2 and 3, which are
          respectively 70% and 60% respectively. So, the total
          of numbers divisible by 2 and 3 between 1 and 100 is
          7+6+7+7+6+7+7+6+7+7=67 out of 100, which is 67%.

          Between 100 and 200.
          6+7+7+6+7+7+6+7+7+6= 66%.

          Trying out a few times and finding the average we see
          that the percentage of numbers divisible by 2 and 3 is
          about 66.67%.

          According to Dr.Schneier's book,testing an odd number
          is not divisible by 3,5,7 eliminates 54% of odd
          numbers under test. It is found in general that the
          fraction of odd candidates which is not a multiple of
          any prime less than n is 1.12/ln n.

          Hope this helps.

          Sarad.



          --- Gary Chaffey <garychaffey2@...> wrote:

          > As usual a typo on my formula!
          > I know it was just an example but if K is not
          > divisible by 2 or 3 then the
          > chance of it being prime is 3/(lnK)
          > Gary
          > garychaffey2 <garychaffey2@...> wrote:
          > Could somebody please give me some online references
          > to information
          > about the benefits of sieving.
          > E.g. Suppose a number K is a random integer then it
          > has a 1 in 1/ln K
          > chance of being prime but if K is not divisible by 2
          > or 3 then the
          > chance of it being prime is 2/(3lnK)
          > etc
          > That type of thing.
          > Thanks in advance
          > Gary




          ____________________________________________________
          Sell on Yahoo! Auctions – no fees. Bid on great items.
          http://auctions.yahoo.com/
        • Phil Carmody
          From: garychaffey2 ... Mertens Theorem. Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML
          Message 4 of 4 , Jul 13, 2005
          • 0 Attachment
            From: "garychaffey2" <garychaffey2@...>
            > Subject: Benefits of sieving. References please
            >
            > Could somebody please give me some online references to information
            > about the benefits of sieving.

            Mertens' Theorem.

            Phil

            () ASCII ribbon campaign () Hopeless ribbon campaign
            /\ against HTML mail /\ against gratuitous bloodshed

            [stolen with permission from Daniel B. Cristofani]

            __________________________________________________
            Do You Yahoo!?
            Tired of spam? Yahoo! Mail has the best spam protection around
            http://mail.yahoo.com
          Your message has been successfully submitted and would be delivered to recipients shortly.