Efficiently finding a linear progression in data - Page 3

chris2be8 · 2015-10-29, 19:10

I was really wondering if replacing 2^16384 with a similar sized primorial would increase the chance of a given n generating a prime enough to make the search feasible.

But p1-x-p2 can generate a number not in your list. Eg if n=1 and n=2 generate primes their average won't be generated by any n. This happens if one prime is generated by an odd n and one prime by an even n. Weather it's worth a primality test is another matter.

Chris

science_man_88 · 2015-10-29, 19:25

Quote:

Originally Posted by science_man_88

Code:

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.

realizing about primes I may be able to trim my pari code even more in the c values because if for example:

distance is a multiple of 3:

3x+1->3y+1
3x+2->3y+2

distance is 1 mod 3:

3x+1->3y+2; 3x+1 fails going down.
3x+2; fails going up

distance is 2 mod 3:
3x+1 fails going up
3x+2 fails going down. and can only go 1 distance up.

so the distances I check have to be multiples of 3. and for longer AP clearly eventually one hits a multiple of another prime. I know this should be obvious ...

science_man_88 · 2015-10-30, 20:06

the other hard part I see is that you can restate this like primes in a set have form 2kp+1 for a specific value $p,k\in \mathb{N}$ (p constant) and asking if k differences are the same for example, but with the original number this makes it more work than to check differences I'd think.

science_man_88 · 2015-10-31, 13:07

oh and if we have 2n+1, n odd, then we can keep on going down to figure out if they are equidistant because we could have say 2(2n+1)+1 are only equidistant when the numbers 2n+1 are equidistant which only happens when n are equidistant ( in theory you can do this even with n even because one part of it has to be equidistant to the numbers you start with to be equidistant but you might be able bring the numbers you use to test this down quite a few bit levels.

fivemack · 2015-12-12, 18:07

225714205 229747486 233780767 237814048

Four numbers in arithmetic progression, with n*2^32768+1 prime.

I think this is the case with smallest largest term

Batalov · 2015-12-12, 18:42

I got interested in parallel, and recently ran a bit with AP4 and AP5s.

Skipping to the more interesting AP5, I used the following iterative approach:
1. Sieve a largish range for k*p#-1 (or +1 but -1 was the road less traveled, so I used it) with NewPGen, reasonably deeply
2. Extract some modular class (I used k%12==5) and find all primes (here, 12 helps the next step 3 to work)
3. For all pairs of primes (let's mark them "x"), explore following patterns ...xx... , ..x.x.. , .x..x. , x...x and retain only those where all "dots" are still in sieve _and_ at least one more is already prime (or at earlier passes, drop the last equirement), that is three out of five
4. Test for primality the least of "dots" in all patterns. If primes found, check the other "dot" in pattern. Exit if set of 5 is found
5. Repeat from Step 2 with additional class (k%12==11, then k%12==8 and 2; then the rest, if necessary)

Found one, then at the clean-up stage found the second set. (Reported to UTM.)

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How do you efficiently sieve for prime 3/4-tuples?	Puzzle-Peter	Software	156	2019-06-03 20:19
Exponent Progression	storm5510	Information & Answers	15	2017-07-26 18:02
Bertrand's Theorem for Arithmetic Progression	literka	Math	0	2013-06-01 12:42
Milestone Progression Update	NBtarheel_33	Data	2	2010-09-02 03:14
nth prime number in an arithmetic progression	Unregistered	Information & Answers	1	2010-04-04 22:06

2015-10-29, 19:10	#23
chris2be8 Sep 2009 2·1,039 Posts	I was really wondering if replacing 2^16384 with a similar sized primorial would increase the chance of a given n generating a prime enough to make the search feasible. But p1-x-p2 can generate a number not in your list. Eg if n=1 and n=2 generate primes their average won't be generated by any n. This happens if one prime is generated by an odd n and one prime by an even n. Weather it's worth a primality test is another matter. Chris

2015-10-30, 20:06	#25
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶×131 Posts	the other hard part I see is that you can restate this like primes in a set have form 2kp+1 for a specific value $p,k\in \mathb{N}$ (p constant) and asking if k differences are the same for example, but with the original number this makes it more work than to check differences I'd think.

2015-10-31, 13:07	#26
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶·131 Posts	oh and if we have 2n+1, n odd, then we can keep on going down to figure out if they are equidistant because we could have say 2(2n+1)+1 are only equidistant when the numbers 2n+1 are equidistant which only happens when n are equidistant ( in theory you can do this even with n even because one part of it has to be equidistant to the numbers you start with to be equidistant but you might be able bring the numbers you use to test this down quite a few bit levels.

2015-12-12, 18:07	#27
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1913₁₆ Posts	225714205 229747486 233780767 237814048 Four numbers in arithmetic progression, with n*2^32768+1 prime. I think this is the case with smallest largest term

2015-12-12, 18:42	#28
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	I got interested in parallel, and recently ran a bit with AP4 and AP5s. Skipping to the more interesting AP5, I used the following iterative approach: 1. Sieve a largish range for k*p#-1 (or +1 but -1 was the road less traveled, so I used it) with NewPGen, reasonably deeply 2. Extract some modular class (I used k%12==5) and find all primes (here, 12 helps the next step 3 to work) 3. For all pairs of primes (let's mark them "x"), explore following patterns ...xx... , ..x.x.. , .x..x. , x...x and retain only those where all "dots" are still in sieve _and_ at least one more is already prime (or at earlier passes, drop the last equirement), that is three out of five 4. Test for primality the least of "dots" in all patterns. If primes found, check the other "dot" in pattern. Exit if set of 5 is found 5. Repeat from Step 2 with additional class (k%12==11, then k%12==8 and 2; then the rest, if necessary) Found one, then at the clean-up stage found the second set. (Reported to UTM.)