View Single Post
 2011-08-19, 16:09 #6 jasonp Tribal Bullet     Oct 2004 67168 Posts I might as well make this thread the dumping ground for all the problems I have with arithmetic progressions. Here's the latest, a consequence of an insidious bug in msieve that I'm trying to fix: Suppose you have a bunch of different arithmetic progressions R0 + i * p^k where p is prime and p^k is small (say less than 1000). There are lots of different R0, up to p^k of them. I need to 'map' each of these progressions onto a lattice of size L, i.e. to find another arithmetic progression R0' + j * p^k such that every value of that second progression lies on a lattice A + m * L. When L and p^k are coprime this is easy, and was addressed by Bob's post above. In fact with many R0 you can find R0' via a single table lookup: maintain an array of size p^k and put j at location (A+j*L) mod p^k for each j in turn, so that R0' = table[R0]. What I evidently don't understand is what to do when p divides L one or more times. I originally assumed that the table lookup method described above still works, except that - R0' may not exist depending on the precise value of A and L - the new progression would have a step value of p^k / gcd(L, p^k) and not p^k but I've noticed numerical examples where that's not true. Rather than trying to fit a heuristic to data, I was wondering how to solve this (embarrassingly easy sounding) problem analytically.