Yeah, there's no reason to omit those singletons. I don't need any approximation, but would be interested in the best one available. —Dan
On Jun 15, 2016, at 1:50 PM, Marc LeBrun <mlb@well.com> wrote:
="Dan Asimov" <asimov@msri.org> ... we want to estimate the number #(x; N, q) of positive integers <= x that are product of numbers of the form kN + q, Heuristically, for each integer X <= x this should be pretty close to the case where q = 0. ...then YIKES... There must be a better way.
If I understand aright, it seems maybe you're worrying yourself overmuch? Note that in the odd numbers example you included all the odd primes, but in your 5N+4 example you omitted the 30 singletons 4, 19, ... 144, 149. These are the most common form of "products", approximately x/N in all. For closer estimates you can indeed add terms for the pairs, triples, etc, and subtract for duplicates, etc. How sharp an approximation do you need?