sieving primes in arithmetic progressions

[maxal]

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.

[paulunderwood]

When Markus Frind and myself looked for a titanic AP-8 we used a four step process:

1. sieve with newpgen a form with 2411# in it to give a high density
2. PRP with PFGW
3. use Markus' ap-detector on the PrP points extending beyond the range when an AP-7 was detected
4. 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!

[paulunderwood]

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

[3.14159]

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.

[bsquared]

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?

[maxal]

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).

[fivemack]

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<i<j<N and checking 2x_j-x_i; and it feels as if it ought to be possible to use some kind of Fourier-transform autocorrelation approach, though the naive way would use memory on the order of the size of the numbers rather than on the order of the size of the set.

Can it be done in n log n time and memory?

[maxal]

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.