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

Re: AP Question

Expand Messages
  • 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 1 of 3 , Apr 28 11:20 AM
      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 2 of 3 , Apr 28 11:21 AM
        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.