10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A couple of questions first: What is the rough magnitude of the numbers $A$ and $B$ (tens? thousands? millions?)? What are the memory restrictions? Do you need all the pairs available at the same time in memory, or is it okay if they're generated one by one? Is the trivial algorithm (just generate all pairs and compute their GCD) too slow for your purposes? $\endgroup$ – Peter Košinár Jun 17 '13 at 15:39
  • 1
    $\begingroup$ A and B might go as high as 40000 each or so. Nothing huge, but large enough to get irritating. Generated one by one is okay. $\endgroup$ – MyNameIsKhan Jun 17 '13 at 15:45
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.