## AP Question

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