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

Re: [PrimeNumbers] Benefits of sieving. References please

Expand Messages
  • 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 1 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 2 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.