9
$\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
5
$\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$

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.