20101003, 17:38  #12  
Feb 2005
2^{2}·3^{2}·7 Posts 
Quote:
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 20101003 at 17:39 

20101003, 17:55  #13 
Sep 2002
Database er0rr
2^{2}×919 Posts 
When Markus Frind and myself looked for a titanic AP8 we used a four step process:
http://listserv.nodak.edu/cgibin/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! 
20101003, 18:25  #14 
Sep 2002
Database er0rr
2^{2}×919 Posts 
For the titanic AP9...
Last fiddled with by paulunderwood on 20101003 at 18:56 
20101004, 01:49  #15 
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
Just make a nice script, hope that it's fast, and continue on from there.
Last fiddled with by 3.14159 on 20101004 at 01:51 
20101004, 05:09  #16  
"Ben"
Feb 2007
6556_{8} Posts 
Quote:


20101004, 16:30  #17 
Feb 2005
2^{2}·3^{2}·7 Posts 
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 MillerRabin).

20101004, 16:54  #18 
(loop (#_fork))
Feb 2006
Cambridge, England
6384_{10} 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<i<j<N and checking 2x_jx_i; and it feels as if it ought to be possible to use some kind of Fouriertransform 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? Last fiddled with by fivemack on 20101004 at 16:56 
20101004, 17:11  #19 
Feb 2005
2^{2}·3^{2}·7 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Arithmetic progressions for n  MattcAnderson  MattcAnderson  28  20170508 20:58 
Compositions of arithmetic progressions  jasonp  Factoring  8  20110820 13:42 
Sieving for primes  CRGreathouse  Math  0  20090106 14:38 
Detecting arithmetic progressions  grandpascorpion  Math  18  20070328 15:08 
Arithmetic and Polynomial Progression of Primes?  drake2  Math  13  20061010 00:43 