mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2010-10-03, 17:38   #12
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by axn View Post
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
maxal is offline   Reply With Quote
Old 2010-10-03, 17:55   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,533 Posts
Default

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 is offline   Reply With Quote
Old 2010-10-03, 18:25   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

353310 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2010-10-04, 01:49   #15
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

Quote:
Originally Posted by maxal View Post
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
3.14159 is offline   Reply With Quote
Old 2010-10-04, 05:09   #16
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,361 Posts
Default

Quote:
Originally Posted by maxal View Post
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?
bsquared is offline   Reply With Quote
Old 2010-10-04, 16:30   #17
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by bsquared View Post
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).
maxal is offline   Reply With Quote
Old 2010-10-04, 16:54   #18
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,379 Posts
Default

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?

Last fiddled with by fivemack on 2010-10-04 at 16:56
fivemack is offline   Reply With Quote
Old 2010-10-04, 17:11   #19
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Arithmetic progressions for n MattcAnderson MattcAnderson 28 2017-05-08 20:58
Compositions of arithmetic progressions jasonp Factoring 8 2011-08-20 13:42
Sieving for primes CRGreathouse Math 0 2009-01-06 14:38
Detecting arithmetic progressions grandpascorpion Math 18 2007-03-28 15:08
Arithmetic and Polynomial Progression of Primes? drake2 Math 13 2006-10-10 00:43

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

Sat Jan 23 17:23:26 UTC 2021 up 51 days, 13:34, 0 users, load averages: 1.70, 1.88, 1.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.