mersenneforum.org sieving primes in arithmetic progressions
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2010-10-02, 14:14 #1 maxal     Feb 2005 22×32×7 Posts sieving primes in arithmetic progressions Does there exist a fast optimized siever for finding primes in a given arithmetic progression? That is, for given the parameters A, B along with the range [L,U], such siever should find and report all primes of the form A*k + B in the interval [L,U]. It is not a big deal to write my own siever (based on ala sieve of Eratosthenes or Atkin) but I'd rather use a fast existing siever if there is such a beast. Last fiddled with by maxal on 2010-10-02 at 14:15
 2010-10-02, 14:58 #2 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts well to get the candidates just find k such that A*k+B are on the lines 6n+1 or 6n-1.
 2010-10-02, 16:23 #3 Ken_g6     Jan 2005 Caught in a sieve 1100010112 Posts Hm, that kinda looks like k*2^n+1, doesn't it? I may know something about this. Let's see...you want to find: k*A+B = 0 (mod P) k*A = -B (mod P) k = -B*A^-1 (mod P) Now, -B (mod P) is just P-B, assuming B < P. A^-1, on the other hand, is a Modular multiplicative inverse. Those take a little more work, but they can be worth it. Especially if A is of a special form that makes it easy.
 2010-10-02, 16:40 #4 maxal     Feb 2005 FC16 Posts I'm not asking about the theory, I'm asking about the _software_.
2010-10-02, 16:43   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by maxal I'm not asking about the theory, I'm asking about the _software_.
well the first thing the software needs is theory I'm not sure if there is one.

2010-10-02, 16:44   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by maxal I'm not asking about the theory, I'm asking about the _software_.

 2010-10-02, 17:23 #7 maxal     Feb 2005 22×32×7 Posts science_man_88, I asked concrete question about the software - if you don't know the answer, please don't make irrelevant comments. And please don't teach me the theory - believe me, I know it well.
 2010-10-02, 17:41 #8 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts look if you want a siever either build one if you can or look as apparently nothing else is what you want so why post it here.
 2010-10-03, 13:44 #9 mdettweiler A Sunny Moo     Aug 2007 USA (GMT-5) 3×2,083 Posts PrimeGrid did a big search for an AP26 earlier this year; I'm not sure how they went about doing it, but I would assume that a fast sieve was part of it somewhere along the way. You might try asking in their AP26 subproject forum about it.
 2010-10-03, 17:13 #10 maxal     Feb 2005 22·32·7 Posts 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.
 2010-10-03, 17:32 #11 axn     Jun 2003 47·103 Posts yafu has a high performance SoE. It also (most likely) has routines for modular arithmetic. Should be easy to adapt it for your purpose.

 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 09:31.

Sat Jan 16 09:31:30 UTC 2021 up 44 days, 5:42, 0 users, load averages: 1.44, 1.46, 1.48