Generating all coprime pairs within limits

Question

Say I want to generate all coprime pairs ($a,b$) where no $a$ exceeds $A$ and no $b$ exceeds $B$.

Is there an efficient way to do this?

Answer 1

In general, if $(a,b)$ is coprime then $(a-b,b)$ are coprime and $(a,b-a)$ are coprime. So you can just do this by induction, which will take $O(AB)$ time and $O(AB)$ memory.

You can't do it in better time, since there are $O(AB)$ outputs - for large $A,B$, it is about $\frac{6AB}{\pi^2}$ outputs. You can possibly do it in better memory - keeping all the smaller values is a cost.

Answer 2

If $A$ and $B$ are comparable in value, the algorithm for generating Farey sequence might suit you well; it generates all pairs of coprime integers $(a,b)$ with $1\leq a<b\leq N$ with constant memory requirements and $O(1)$ operations per output pair. Running it with $N=\max(A,B)$ and filtering out pairs whose other component exceeds the other bound produces all the coprime pairs you seek.

If the values of $A$ and $B$ differ too much, the time wasted in filtering the irrelevant pairs would be too high and a different approach (such as that suggested by Thomas Andrews) might be necessary.