[Solved]: Counting the number of N-dimensional coprime integer vectors

Problem Detail: 

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.

Asked By : Berk U.

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18552