mersenneforum.org sieving primes in arithmetic progressions
 Register FAQ Search Today's Posts Mark Forums Read

2010-10-03, 17:38   #12
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by axn yafu has a high performance SoE. It also (most likely) has routines for modular arithmetic. Should be easy to adapt it for your purpose.
That may be a good idea, if there is no ready-to-use tool.
Another option is to adapt the PrimeGen tool http://cr.yp.to/primegen.html that uses sieve of Atkin.

Last fiddled with by maxal on 2010-10-03 at 17:39

 2010-10-03, 17:55 #13 paulunderwood     Sep 2002 Database er0rr 22×919 Posts When Markus Frind and myself looked for a titanic AP-8 we used a four step process: sieve with newpgen a form with 2411# in it to give a high density PRP with PFGW use Markus' ap-detector on the PrP points extending beyond the range when an AP-7 was detected prove the 8 PRPs http://listserv.nodak.edu/cgi-bin/wa...RY&P=R410&I=-3 What would be a cool record is a titanic AP 9. Something that should be done in this decade!
 2010-10-03, 18:25 #14 paulunderwood     Sep 2002 Database er0rr 22×919 Posts For the titanic AP-9... we would need 1.2 billion PRPs -- this is not a problem when the work is DC'd on modern hardware a big machine with lots of ram and shared memory access and many cores, like the AMD chips coming out next year -- to do the AP-detection Last fiddled with by paulunderwood on 2010-10-03 at 18:56
2010-10-04, 01:49   #15
3.14159

May 2010
Prime hunting commission.

24·3·5·7 Posts

Quote:
 Originally Posted by maxal AP26 is irrelevant. I'm not looking for primes forming an arithmetic progression, but primes in the given arithmetic progression (possibly with gaps between them). The latter problem is much simpler than the former one.
Just make a nice script, hope that it's fast, and continue on from there.

Last fiddled with by 3.14159 on 2010-10-04 at 01:51

2010-10-04, 05:09   #16
bsquared

"Ben"
Feb 2007

65568 Posts

Quote:
 Originally Posted by maxal That may be a good idea, if there is no ready-to-use tool. Another option is to adapt the PrimeGen tool http://cr.yp.to/primegen.html that uses sieve of Atkin.
I don't know of a ready to use tool, but I also haven't looked. YAFU's SoE is pretty good, but I don't know right away what modifications would be needed to do what you need it to do, so I don't know how easy it would be to accomplish. If it comes to that I'll help you if I can. I've got modular arithmetic routines coded too, but they are home grown and likely not as fast as gmp, especially for larger [L,U]. Speaking of which, what order of magnitude are you interested in for L and U? You mention you would like the software to return primes, which for a sieve implies no more than 10^20 or so. Or would you just like less candidates to test with some other method?

2010-10-04, 16:30   #17
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by bsquared Speaking of which, what order of magnitude are you interested in for L and U? You mention you would like the software to return primes, which for a sieve implies no more than 10^20 or so. Or would you just like less candidates to test with some other method?
In general we can assume L=1. The order of U/A (notice that the "step" A may be large, making it possible to reach larger U) is reasonable - 10^20 or so, as you mentioned. And, indeed, the sieve may be combined with other methods, that is, it would sieve out numbers divisible by "small" primes, delegating (pseudo-)primality proofs of the remaining "candidates" to other methods (such as Miller-Rabin).

 2010-10-04, 16:54 #18 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 638410 Posts How do you do the search for arithmetic progressions in a set of numbers? There's the obvious n^2 log n approach of running through x_i, x_j for 0
2010-10-04, 17:11   #19
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by fivemack How do you do the search for arithmetic progressions in a set of numbers?
I don't, the arithmetic progression (that is, the constants A and B) is given.

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 28 2017-05-08 20:58 jasonp Factoring 8 2011-08-20 13:42 CRGreathouse Math 0 2009-01-06 14:38 grandpascorpion Math 18 2007-03-28 15:08 drake2 Math 13 2006-10-10 00:43

All times are UTC. The time now is 23:38.

Mon May 17 23:38:31 UTC 2021 up 39 days, 18:19, 0 users, load averages: 1.62, 1.98, 2.11