Efficiently finding a linear progression in data

[paulunderwood]

http://primes.utm.edu/top20/sizes.php shows the digit sizes you need for UTM's prime database.

[R.D. Silverman]

Originally Posted by paulunderwood

http://primes.utm.edu/top20/sizes.php shows the digit sizes you need for UTM's prime database.

And?

This is irrelevant and off-topic for the current thread.

[paulunderwood]

I thought I read "n*2^100000+1" and not "n*2^10000+1" in fivemack's post.

[fivemack]

paulunderwood is of course right about my underlying intentions; at the moment I'm warming up, and trying to work out whether I've got enough computrons in my herd to make a realistic attempt at getting at least into the AP4 list, if not the AP4 record.

(I'd be doing it the dumb way, enumerating the primes and then searching for the APs, and of course I realise it's an exercise in persistence and paying electricity bills rather than anything very closely resembling maths)

[chris2be8]

Will the numbers be a mixture of odd and even numbers? If so you can save half the work as follows:

Call the numbers you want A B and C where A-B=B-C (that makes A largest). Search all A, C to see if the average (A+C)/2 is in the set. This can only happen if A and C are both odd or both even so start by splitting the list into two parts, one with the odd numbers and one with the even numbers. Then pick A and C from one list and see if B exists (B could be odd or even so search both lists or the original list). That should save a factor of 2 assuming as many odd as even.

If all the numbers are odd you can do something similar by splitting them into 4n+1 and 4n+3 lists.

If the numbers are all prime you can probably speed it up further by splitting into 12n+1,5,7,11 and only checking cases where A and C are not 3n+1 and 3n+2 since the average will be a multiple of 3. And extend further to skip multiples of 5, 7 etc.

To search for longer progressions you could search for progressions of 3, then check those relatively few cases to see if they extend any further at either end.

Chris

[science_man_88]

a=[1,2,3,4,7,8,100];b=parselect(r->#parselect(c->#setminus(Vec([r-c,r+c]),a)==0,[1..eval(vecmax(a)-r)])!=0,a)

this figures out all middle points in the vector [1,2,3,4,7,8,100].Edit: okay technically the real setminus condition should be >1 because there's a possibility of one side being there but the other not being there. and the outer value can be changed to ==1 if you want those with one distinct linear sequence etc.

[science_man_88]

oh and of course you can use parvector for large vectors and setminus and vecmax have parallel code potentially using parapply or as:


and


respectively.

[Batalov]

Originally Posted by fivemack

paulunderwood is of course right about my underlying intentions; at the moment I'm warming up, and trying to work out whether I've got enough computrons in my herd to make a realistic attempt at getting at least into the AP4 list, if not the AP4 record.

(I'd be doing it the dumb way, enumerating the primes and then searching for the APs, and of course I realise it's an exercise in persistence and paying electricity bills rather than anything very closely resembling maths)

David Broadhurst was employing the clever strategy (every few years) for AP3: wait for others to generate thousands of (otherwise totally useless) primes and then use that as an input for a combinatorial search. When there's a few thousand primes, one finds a few million AP3 candidates by linear combinations (in three ways: p1-p2-x, p1-x-p2, x-p1-p2), and then luckily NewPGen is useful again to sieve the x's all together (works really fast, after getting over the initial arrays to sparse-array transition point).

AP4 and higher, indeed, need another strategy; it is only by very improbable luck an AP4 could be found in the above way.

[fivemack]

Serge is (of course) right.

It seems that the number of terms of a sequence of density D that you need to take in order to hit an arithmetic progression of length N+2 is around D^(-N/2); so you'd want a few tens of thousands of primes of the form n*2^32768+1 to get an AP4, and a few million to get an AP5.

I have found 1425 primes of that form by going over 1<n<2^24 in about 150 CPU-hours on a fast computer, so I could get to a few tens of thousands by Christmas, but an AP4 of primes that small wouldn't be interesting, and finding a few million primes and an AP5 is impractical.

[chris2be8]

If you just want an AP3 (or AP4) with large terms you should be able to speed the search up by:

1: Choosing a primorial of the size you are interested in, x#
2: Search for primes of the form n*x#+1
3: For each pair of primes check if they are part of an AP3 (3 ways, x-p1-p2, p1-x-p2, p1-p2-x as Batalov said above). If they are see if it extends any further.

Since the third term will be of the same form it won't be divisible by any prime below x. Which should increase the chance it's prime. Whether it increases it enough to make the search feasible depends how big an AP3 you want and what resources you have.

Chris

[fivemack]

Originally Posted by chris2be8

If you just want an AP3 (or AP4) with large terms you should be able to speed the search up by:

1: Choosing a primorial of the size you are interested in, x#
2: Search for primes of the form n*x#+1
3: For each pair of primes check if they are part of an AP3 (3 ways, x-p1-p2, p1-x-p2, p1-p2-x as Batalov said above). If they are see if it extends any further.

Assuming that I start by searching some initial segment of the numbers of the form n*x#+1, I'll never get an x-p1-p2 or p1-x-p2 where I don't already know the status of x. If I start with the 23483 primes n*2^16384+1 with n<2^27, extrapolating p1-p2-x gets me 74230413 distinct larger candidates to look at, which isn't a very big reduction on 2^27.