## Re: AP Question

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