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: [url]http://www.shyamsundergupta.com/canyoufind.htm[/url]

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

[QUOTE=grandpascorpion;101789]to search for a number n3 = n1+(n2-n1).[/QUOTE]
But then n3 == n2. :)
I think that you want
n3 = n2 + (n2-n1) = 2*n2-n1

Hi Fred,

If I understand his question:

[QUOTE]Can You Find:
Four numbers in Arithmetical progression whose sum of divisors is same[/QUOTE]
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

[quote=grandpascorpion;101789][URL]http://www.shyamsundergupta.com/canyoufind.htm[/URL]
[/quote]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.

[QUOTE=Wacky;101792]But then n3 == n2. :)
I think that you want
n3 = n2 + (n2-n1) = 2*n2-n1[/QUOTE]

Thanks, that's what I meant :blush:


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.

I came across an interesting website relating to Ruth-Aaron pairs and triplets. Though this works with the sum of prime factors.

[URL="http://www.immortaltheory.com/NumberTheory/RuthAaron.htm"]http://www.immortaltheory.com/NumberTheory/RuthAaron.htm[/URL]

Regards
Patrick

[QUOTE=Patrick123;101843]I came across an interesting website relating to Ruth-Aaron pairs and triplets. Though this works with the sum of prime factors.

[URL="http://www.immortaltheory.com/NumberTheory/RuthAaron.htm"]http://www.immortaltheory.com/NumberTheory/RuthAaron.htm[/URL][/QUOTE]

I found better algorithms and computational results at [url]http://www.primepuzzles.net/puzzles/puzz_358.htm[/url]

[QUOTE=Jens K Andersen;101866]I found better algorithms and computational results at [url]http://www.primepuzzles.net/puzzles/puzz_358.htm[/url][/QUOTE]

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

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));
}

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)

:bow: 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