 mersenneforum.org > Math Detecting arithmetic progressions
 Register FAQ Search Today's Posts Mark Forums Read  2007-03-22, 21:52 #1 grandpascorpion   Jan 2005 Transdniestr 1111101112 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+(n2-n1). Then if that exists, I do another binary search for n4 = n3 + (n2-n1). This is ok but understandably quite slow once the list to search gets into the thousands. Thanks, Fred   2007-03-22, 22:19   #2
Wacky

Jun 2003
The Texas Hill Country

44116 Posts Quote:
 Originally Posted by grandpascorpion to search for a number n3 = n1+(n2-n1).
But then n3 == n2. :)
I think that you want
n3 = n2 + (n2-n1) = 2*n2-n1   2007-03-22, 22:21   #3
Patrick123

Jan 2006
JHB, South Africa

2358 Posts Hi Fred,

If I understand his question:

Quote:
 Can You Find: Four numbers in Arithmetical progression whose sum of divisors is same
Does he mean, the sum of divisors would also be an Arithmetical Progression or the would all be the same value?

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 2007-03-22 at 22:34 Reason: Had an epiphany   2007-03-22, 22:39   #4

"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts Quote:
 Originally Posted by grandpascorpion http://www.shyamsundergupta.com/canyoufind.htm
Wow! Lots of good problems there, and some have been sitting unsolved for more than 5 years (nrs. 6, 9, 10). Also, some solutions pose a related problem, so read through them all.   2007-03-22, 23:29   #5
grandpascorpion

Jan 2005
Transdniestr

503 Posts Quote:
 Originally Posted by Wacky But then n3 == n2. :) I think that you want n3 = n2 + (n2-n1) = 2*n2-n1
Thanks, that's what I meant 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*(n2-n1) > max solution, there's no point search any further on the n1 value.   2007-03-23, 11:44 #6 Patrick123   Jan 2006 JHB, South Africa 157 Posts I came across an interesting website relating to Ruth-Aaron 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 2007-03-23 at 11:52   2007-03-23, 15:12   #7
Jens K Andersen

Feb 2006
Denmark

E616 Posts Quote:
 Originally Posted by Patrick123 I came across an interesting website relating to Ruth-Aaron pairs and triplets. Though this works with the sum of prime factors. http://www.immortaltheory.com/Number.../RuthAaron.htm
I found better algorithms and computational results at http://www.primepuzzles.net/puzzles/puzz_358.htm   2007-03-23, 15:16   #8
Patrick123

Jan 2006
JHB, South Africa

157 Posts Quote:
 Originally Posted by Jens K Andersen I found better algorithms and computational results at http://www.primepuzzles.net/puzzles/puzz_358.htm
I saw that the footnotes, point to puzzle 173, and I assumed Fred would logically follow the appropriate chains, but thanks for pointing out #358, I would have most probably missed it.

Regards
Patrick   2007-03-24, 00:18 #9 grandpascorpion   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((r-1)/3); num4aps = r*m-3*m*(m+1)/2; choose4range = binomial(r,4); choose4sols = binomial(n,4); return(1-(1-num4aps/choose4range)^(choose4sols)); }   2007-03-25, 22:16 #10 grandpascorpion   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)   2007-03-26, 07:31 #11 Patrick123   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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post mathPuzzles Computer Science & Computational Number Theory 9 2017-07-01 03:35 MattcAnderson MattcAnderson 28 2017-05-08 20:58 VoltsNCodes Msieve 13 2013-06-14 15:14 jasonp Factoring 8 2011-08-20 13:42 maxal Software 18 2010-10-04 17:11

All times are UTC. The time now is 00:31.

Sun Jan 17 00:31:28 UTC 2021 up 44 days, 20:42, 0 users, load averages: 1.85, 1.63, 1.55