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

AP Question

Expand Messages
  • Gary Chaffey
    Suppose I have a large number of primes say 10^5-10^6 What is the quickest/most effective way to look for APs among them? My idea is to put them all into an
    Message 1 of 3 , Apr 28 9:29 AM
    • 0 Attachment
      Suppose I have a large number of primes say 10^5-10^6
      What is the quickest/most effective way to look for
      APs among them?
      My idea is to put them all into an array in order of
      size.
      Call the smallest a1 next a2 etc
      Then say a2-a1=b
      see if a3-a2=b if so AP3
      else if a3-a2>b then stop this loop
      else a3-a2<b so now check a4-a2
      if a4-a2=b if so AP3
      else if a4-a2>b then stop this loop
      else a4-a2<b so now check a5-a2 etc
      Once this loop has stopped
      reset b to a3-a2
      then re-run the loop starting with
      a4-a3
      etc
      Is this the best approach??
      Gary



      __________________________________________________
      Yahoo! Plus
      For a better Internet experience
      http://www.yahoo.co.uk/btoffer
    • Markus
      Jim has the fastest generic AP detection APP, but when the primes are less then 100 digits or so my application/3D Sieve is orders of magnitude faster. Given
      Message 2 of 3 , Apr 28 11:20 AM
      • 0 Attachment
        Jim has the fastest generic AP detection APP, but when the primes
        are less then 100 digits or so my application/3D Sieve is orders of
        magnitude faster.

        Given 1..5 million * 7#+1
        You want to find all AP 6's

        (10+11*k)+7#+1 is divisible by 11.

        If we look at 1*7#+1 we notice the following gaps will create a AP
        6 not divisible by 11.

        1 = 1,2,3,4,5,6
        2 = 1,3,5,7,9,11
        3= 1,4,7,10,13,16 ( doesn't work because it intersects (10+11*k)
        +7#+1)
        4= 1,5,9,13,17,21 ( doesn't work because it intersects (10+11*k)
        +7#+1)
        5= 1,6,11,16,21,26 ( doesn't work because it intersects (10+11*k)
        +7#+1)
        6= 1,7,13,19,25,31
        7= 1,8,15,22,29,36
        8= 1,9,17,25,33,41
        9= 1,10,19,28,37,46 ( doesn't work because it intersects (10+11*k)
        +7#+1)
        10=1,11,21,31,41,51
        11=1,12,23,34,45,56


        We can now say that if Gap MOD 11 is = (1 or 2 or 6 or 7 or 8 or 10
        or 11) then (1+11*k)*7#+1 will form a AP6 that is not divisible by
        11. This reduces our search space by 4/11 or 36.36%

        Now i used something similar method to find my AP22, except i used
        primes up to 59 and searched the series 1..5 million *23#+x and this
        range was searched in under 30 seconds...

        Markus




        --- In primenumbers@yahoogroups.com, Gary Chaffey <garychaffey@y...>
        wrote:
        > Suppose I have a large number of primes say 10^5-10^6
        > What is the quickest/most effective way to look for
        > APs among them?
        > My idea is to put them all into an array in order of
        > size.
        > Call the smallest a1 next a2 etc
        > Then say a2-a1=b
        > see if a3-a2=b if so AP3
        > else if a3-a2>b then stop this loop
        > else a3-a2<b so now check a4-a2
        > if a4-a2=b if so AP3
        > else if a4-a2>b then stop this loop
        > else a4-a2<b so now check a5-a2 etc
        > Once this loop has stopped
        > reset b to a3-a2
        > then re-run the loop starting with
        > a4-a3
        > etc
        > Is this the best approach??
        > Gary
        >
        >
        >
        > __________________________________________________
        > Yahoo! Plus
        > For a better Internet experience
        > http://www.yahoo.co.uk/btoffer
      • Markus
        Jim has the fastest generic AP detection APP, but when the primes are less then 100 digits or so my application/3D Sieve is orders of magnitude faster. Given
        Message 3 of 3 , Apr 28 11:21 AM
        • 0 Attachment
          Jim has the fastest generic AP detection APP, but when the primes
          are less then 100 digits or so my application/3D Sieve is orders of
          magnitude faster.

          Given 1..5 million * 7#+1
          You want to find all AP 6's

          (10+11*k)+7#+1 is divisible by 11.

          If we look at 1*7#+1 we notice the following gaps will create a AP
          6 not divisible by 11.

          1 = 1,2,3,4,5,6
          2 = 1,3,5,7,9,11
          3= 1,4,7,10,13,16 ( doesn't work because it intersects (10+11*k)
          +7#+1)
          4= 1,5,9,13,17,21 ( doesn't work because it intersects (10+11*k)
          +7#+1)
          5= 1,6,11,16,21,26 ( doesn't work because it intersects (10+11*k)
          +7#+1)
          6= 1,7,13,19,25,31
          7= 1,8,15,22,29,36
          8= 1,9,17,25,33,41
          9= 1,10,19,28,37,46 ( doesn't work because it intersects (10+11*k)
          +7#+1)
          10=1,11,21,31,41,51
          11=1,12,23,34,45,56


          We can now say that if Gap MOD 11 is = (1 or 2 or 6 or 7 or 8 or 10
          or 11) then (1+11*k)*7#+1 will form a AP6 that is not divisible by
          11. This reduces our search space by 4/11 or 36.36%

          Now i used something similar method to find my AP22, except i used
          primes up to 59 and searched the series 1..5 million *23#+x and this
          range was searched in under 30 seconds...

          Markus



          --- In primenumbers@yahoogroups.com, Gary Chaffey <garychaffey@y...>
          wrote:
          > Suppose I have a large number of primes say 10^5-10^6
          > What is the quickest/most effective way to look for
          > APs among them?
          > My idea is to put them all into an array in order of
          > size.
          > Call the smallest a1 next a2 etc
          > Then say a2-a1=b
          > see if a3-a2=b if so AP3
          > else if a3-a2>b then stop this loop
          > else a3-a2<b so now check a4-a2
          > if a4-a2=b if so AP3
          > else if a4-a2>b then stop this loop
          > else a4-a2<b so now check a5-a2 etc
          > Once this loop has stopped
          > reset b to a3-a2
          > then re-run the loop starting with
          > a4-a3
          > etc
          > Is this the best approach??
          > Gary
          >
          >
          >
          > __________________________________________________
          > Yahoo! Plus
          > For a better Internet experience
          > http://www.yahoo.co.uk/btoffer
        Your message has been successfully submitted and would be delivered to recipients shortly.