Generating all coprime pairs within limits

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?

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.

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.

From the wikipedia page for "Coprime integers" (https://en.wikipedia.org/wiki/Coprime_integers):

Generating all coprime pairs

All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint complete ternary trees, one tree starting from $(2,1)$ (for even-odd and odd-even pairs), and the other tree starting from $(3,1)$ (for odd-odd pairs). The children of each vertex $(m,n)$ are generated as follows:

• Branch 1: $(2m-n,m)$
• Branch 2: $(2m+n,m)$
• Branch 3: $(m+2n,n)$

This scheme is exhaustive and non-redundant with no invalid members.

For programming purposes:
Knowing that every child has greater $m$ than its parent, the tree can be generated depth first following, at each node, the first available branch that fulfills $m<A$ until all three are exhausted. When a node has exhausted its three branches, the parent node can be generated without any extra information knowing the branch used to generate the current node:

if $((2n-m)≥0)$, branch 1
else if $(3n≥m)$, branch 2
else, branch 3

with branch and current node, generate parent node and then follow the next available branch to the one already explored. Following this method, it is possible to generate both trees $(2,1)$ and $(3,1)$ starting with these two nodes and ending when $(1,0)$ and $(1,1)$ are reached respectively.

This allows the programming of a function with inputs the current node and the limit and outputs the next node in the tree.