how many ways you can take 4 integers from the N numbers such that their GCD is 1

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1.

for n=5 and the given numbers are.. 1 2 4 6 8 the answer is 4. how to calculate it?

  • $\begingroup$ Do you know any properties of the numbers? For example, if I choose for the same n=5 the numbers 2,3,5,7,11 then the answer will be 5 choose 3 whereas in your example the calculation is 4 choose 3 as 1 with any 3 other numbers will work and the other 4 values have a common factor of 2. $\endgroup$ – JB King Apr 1 '15 at 20:24
  • $\begingroup$ You can just take a prime in, and avoid that the 3 other numbers are divisible with that prime? Then the statement is true. $\endgroup$ – Atvin Apr 1 '15 at 20:24
  • $\begingroup$ if no one is prime from n numbers, what will be the calculation? for example :- 4 ,9 ,15, 21,49 @Atvin $\endgroup$ – Shakhawat Hossain Apr 1 '15 at 20:31
  • $\begingroup$ the numbers will be positive integers and they may not be distinct. @JB King $\endgroup$ – Shakhawat Hossain Apr 1 '15 at 20:32
  • $\begingroup$ If all subsets with exactly 4 elements have a GCD of 1 then the answer is 5 choose 4 which is 5 since it is a matter of considering which integer is missing. Course if all 5 integers share a common factor greater than 1 then the answer is 0. For example if the numbers were 2 4 8 16 32, then there isn't any set that would work. $\endgroup$ – JB King Apr 1 '15 at 20:39

Counting $k$-subsets of $N$ integers whose gcd is $1$ is equivalent to the problem of counting set covers:

Given a set $X$, and a family $\cal F$ of $N$ subsets of $X$, count the $k$-subsets of $\cal F$ whose union is $X$.

To see this, let $X$ be the set of primes dividing any of the $N$ integers, and then identify each integer with the set of primes in $X$ not dividing that integer. Then the gcd of a set of $k$ integers is $1$ iff the union of the corresponding $k$ sets is all of $X$.

Set cover problems are difficult in general. Finding the minimum size of a set cover is known to be NP-hard. van Rooij [vR] gives an exponential-time algorithm for counting set covers. In general, an efficient algorithm is exceedingly unlikely. So, especially if $k$ is fixed at $4$, simply trying all $k$-subsets is a reasonable algorithm.

[vR] Johan M. M. van Rooij, Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number. In Algorithms and Complexity: 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010, Proceedings (Google eBook).

  • $\begingroup$ you can not count all subset . here n=100000, so the number of subset will be nc4 is a large number. I need an algorithm of order n or n*log(n). @Tad $\endgroup$ – Shakhawat Hossain Apr 5 '15 at 16:04

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.