20070322, 21:52  #1 
Jan 2005
Transdniestr
111110111_{2} Posts 
Detecting arithmetic progressions
Hello,
Could anyone recommend a fast algorithm for detecting arithmetic progressions in a list of randomly distributed sorted integers? Ideally, it wouldn't use much memory. I'm working on the current problem at: http://www.shyamsundergupta.com/canyoufind.htm My algorithm that requires searching lists of up to several thousand integers for short arithmetic progressions. All that's necessary is a list of 4 to solve the problem. It's quite an interesting problem if anyone wishes to tackle it. Anyways, right now, I just pick the first two numbers n1, n2 via a double for loop and then use a binary search to search for a number n3 = n1+(n2n1). Then if that exists, I do another binary search for n4 = n3 + (n2n1). This is ok but understandably quite slow once the list to search gets into the thousands. Thanks, Fred 
20070322, 22:19  #2 
Jun 2003
The Texas Hill Country
441_{16} Posts 

20070322, 22:21  #3  
Jan 2006
JHB, South Africa
235_{8} Posts 
Hi Fred,
If I understand his question: Quote:
I think 1, 3, 5, 7 giving 2, 4, 6, 8 respectively be correct for the first option, so obviously it must be the latter. Regards Patrick Last fiddled with by Patrick123 on 20070322 at 22:34 Reason: Had an epiphany 

20070322, 22:39  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
Quote:


20070322, 23:29  #5  
Jan 2005
Transdniestr
503 Posts 
Quote:
Patrick, They are asking four numbers in arithmetic progression such that they all have same sum of divisors. I have been searching by divisor sum using a recursive function and it's quite easy for to find a number with many values that form a.p. with 3 numbers. Four is elusive but I have only checked through 30 million so far. The bit to find the solution set is quite speedy; the bottleneck is with the a.p. search. I did find one simple trick to double the speed of the search. If n2 + 2*(n2n1) > max solution, there's no point search any further on the n1 value. 

20070323, 11:44  #6 
Jan 2006
JHB, South Africa
157 Posts 
I came across an interesting website relating to RuthAaron pairs and triplets. Though this works with the sum of prime factors.
http://www.immortaltheory.com/Number.../RuthAaron.htm Regards Patrick Last fiddled with by Patrick123 on 20070323 at 11:52 
20070323, 15:12  #7  
Feb 2006
Denmark
E6_{16} Posts 
Quote:


20070323, 15:16  #8  
Jan 2006
JHB, South Africa
157 Posts 
Quote:
Regards Patrick 

20070324, 00:18  #9 
Jan 2005
Transdniestr
503 Posts 
This is interesting but a totally different problem: sum of prime factors vs. CYF's sum of divisors.
By the way, I see know why I haven't found any solutions: I picked the number n between 20 and 50 million with s solutions (numbers such that their divisor sum = n) such that log(n)/log(s) was minimized. Assuming the solutions were randomly distributed, I compute the odds of an ap sequence of 4 among s solutions in the range from minSolution to maxSolution. The number is 43545600 and has 4289 solutions. log(n)/log(s)=2.103027 The min solution is 9646560, the max is: 43532389. Assuming my logic is correct the odds of finding one or more ap sequences of length 4 given 4289 random numbers in that range is only 4.78%. get4Odds(n,r) ={ m=floor((r1)/3); num4aps = r*m3*m*(m+1)/2; choose4range = binomial(r,4); choose4sols = binomial(n,4); return(1(1num4aps/choose4range)^(choose4sols)); } 
20070325, 22:16  #10 
Jan 2005
Transdniestr
503 Posts 
Solution to CYF35 found and reported
Yesterday I found a solution to CYF35 that is likely minimal. I wrote a program in PARI to search for all solutions by divisor sum N. Initially, I limited the search to multiples of 24 but found that the number of a.p.'s of length 3 was very small unless there was a high number of divisors of N. So, I limited the search to numbers where numDivisors(N)^3 > N. The other day , I added a 2nd check to find the odds of an a.p. of length 4 given there were X solutions between the maxSolution and the minSolution (and assuming that the solutions were randomly distributed).
For a candidate, if there was < 1% chance of finding an a.p. , I would skip over it. Roughly, only about 1 in million numbers are considered around the 100 million mark. So, an exhaustive search was not performed through this point but it's likely that this is minimal. I reported this solution to the site: 119508480 = 2^9 * 3^3 * 5 * 7 * 13 * 19 4 terms in arithmetic progression with difference: 2138892 = 2^2 * 3 * 7 * 25463 34560288 = 2^5 * 3^2 * 7^2 * 31 * 79 (sumDivs = 31 * 13 * 57 * 32 * 80 = 119508480) 36699180 = 2^2 * 3 * 5 * 7 * 59 * 1481 (sumDivs = 7 * 4 * 6 * 8 * 60 * 1482 = 119508480 ) 38838072 = 2^3 * 3 * 7 * 13 * 17783 (sumDivs = 15 * 4 * 8 * 14 * 17884 = 119508480) 40976964 = 2^2 * 3^2 * 7 * 113 * 1439 (sumDivs = 7 * 13 * 8 * 114 * 1440 = 119508480) 
20070326, 07:31  #11 
Jan 2006
JHB, South Africa
157 Posts 
Congratulations!
I took the approach of generating a text file  "sum of divisors", "number". 10 Million numbers at a time about 200MB . I then used the normal sort utility in M$ to sort it, and now I was about to write the program to do a sequential read of the file and pick any a.p.'s. Regards Patrick 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Detecting bigInt roots  mathPuzzles  Computer Science & Computational Number Theory  9  20170701 03:35 
Arithmetic progressions for n  MattcAnderson  MattcAnderson  28  20170508 20:58 
Problem detecting GPU  VoltsNCodes  Msieve  13  20130614 15:14 
Compositions of arithmetic progressions  jasonp  Factoring  8  20110820 13:42 
sieving primes in arithmetic progressions  maxal  Software  18  20101004 17:11 