View Single Post
Old 2011-08-19, 16:09   #6
Tribal Bullet
jasonp's Avatar
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.
jasonp is offline   Reply With Quote