2
$\begingroup$

I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors.

The vectors in my set are $N$-dimensional integer vectors whose components are bounded on the top and bottom by an arbitrary value $K$. Let $x = [x_1,x_2,\ldots,x_N]$ denote a vector from this set. Then $x$ is coprime if the greatest common denominator of all its elements is 1. That is, $\gcd(x_1,x_2,...,x_N)=1$.

Some 3-dimensional coprime vectors include: $x = [1,2, 3] , [6, 10, 15] ,[0, 1, 1]$
Some 3-dimensional non-coprime vectors include: $x = [2,4,6] ,[0, 10, 15] ,[0, 12, 12]$

For fixed $N$ and $K$, my set contains a total of $(2K+1)^N$ distinct integer vectors as each of the $N$ elements can take on integer values from $-K,\ldots,0,\ldots,K$. A brute-force approach for counting the number of coprime vectors consists of iterating over each of the $(2K+1)^N$ possible vectors and checking to see whether they are coprime (using, for instance, this function). Unfortunately, this approach quickly runs into time and memory issues for large values of $N$ and $K$.

I am wondering if anyone can think of a way to smart algorithm to do this. Ideally, I am looking to implement this algorithm as a MATLAB function that can number of coprime pairs given $N$ and $K$ as its input.

$\endgroup$

1 Answer 1

2
$\begingroup$

For $N=2$, the problem is easy: count the number of non-coprime pairs, by expressing it as a union over all possible values for their common divisor. In particular, a pair $(x_1,x_2)$ is not coprime if there exists a $d>1$ such that $d|x_1$ and $d|x_2$; for fixed $d$, it's easy to count the number of such pairs, so now just sum over all possible values of $d$.

For $N=3$, you could try using the following characterization:

  • $\gcd(x_1,x_2,x_3)=1$ iff either (a) $\gcd(x_1,x_2)=1$, or (b) $\gcd(x_1,x_2)>1$ (so define $d=\gcd(x_1,x_2)$) and $\gcd(d,x_3)=1$.

These two conditions are mutually exclusive, so you can count the number of type-(a) triples and the number of type-(b) triples and then sum those two numbers, to get the number of co-prime triples.

You can count the number of triples of type-(a) quickly (by reducing to the $N=2$ case). You can also count the number of triples of type-(b) quickly, by summing over all possible values of $d$ (for fixed $d$, the number of type-(b) tuples with a particular value of $d$ reduces to a smaller version of your problem with $N=2$ and a smaller value of $K$).

I think you can probably see how to generalize this to larger $N$, giving you a recursive algorithm to solve your problem for general $N$. I'll let you work out the details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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