mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-03-22, 21:52   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default 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
grandpascorpion is offline   Reply With Quote
Old 2007-03-22, 22:19   #2
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

44116 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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
Wacky is offline   Reply With Quote
Old 2007-03-22, 22:21   #3
Patrick123
 
Patrick123's Avatar
 
Jan 2006
JHB, South Africa

2358 Posts
Default

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
Patrick123 is offline   Reply With Quote
Old 2007-03-22, 22:39   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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.
cheesehead is offline   Reply With Quote
Old 2007-03-22, 23:29   #5
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Quote:
Originally Posted by Wacky View Post
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.
grandpascorpion is offline   Reply With Quote
Old 2007-03-23, 11:44   #6
Patrick123
 
Patrick123's Avatar
 
Jan 2006
JHB, South Africa

157 Posts
Default

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
Patrick123 is offline   Reply With Quote
Old 2007-03-23, 15:12   #7
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

E616 Posts
Default

Quote:
Originally Posted by Patrick123 View Post
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
Jens K Andersen is offline   Reply With Quote
Old 2007-03-23, 15:16   #8
Patrick123
 
Patrick123's Avatar
 
Jan 2006
JHB, South Africa

157 Posts
Default

Quote:
Originally Posted by Jens K Andersen View Post
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
Patrick123 is offline   Reply With Quote
Old 2007-03-24, 00:18   #9
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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));
}
grandpascorpion is offline   Reply With Quote
Old 2007-03-25, 22:16   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default 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)
grandpascorpion is offline   Reply With Quote
Old 2007-03-26, 07:31   #11
Patrick123
 
Patrick123's Avatar
 
Jan 2006
JHB, South Africa

157 Posts
Default

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
Patrick123 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Detecting bigInt roots mathPuzzles Computer Science & Computational Number Theory 9 2017-07-01 03:35
Arithmetic progressions for n MattcAnderson MattcAnderson 28 2017-05-08 20:58
Problem detecting GPU VoltsNCodes Msieve 13 2013-06-14 15:14
Compositions of arithmetic progressions jasonp Factoring 8 2011-08-20 13:42
sieving primes in arithmetic progressions 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.