0
$\begingroup$

I have 'n' number of positive integers. I want to find the number of coprime pairs such that none of the pair elements belong to the same group.

For example, if my number sequence is 3,11,7,5,2,6

All possible pairs are:

(3,11),(3,7),(3,5),(3,2),(3,6),(11,7),(11,5),(11,2),(ll,6),(7,5),(7,2),(7,6),(5,2),(5,6),(2,6)

Now calculating the answer as follows:

(3,11) is a coprime. Let's form a group g1[3,11]. Increment answer.
(3,7) is a coprime. 3 belongs to g1, but 7 is not in g1 so adding 7 to g1 to form [3,11,7]. Increment answer.
(3,5) is a coprime. 3 belongs to g1 but 5 is not in g1 so adding 5 to g1 to form [3,11,7,5]. Increment answer.
(3,2) is a coprime. 3 belongs to g1 but 2 is not in g1 so adding 2 to g1 to form [3,11,7,5,2]. Increment answer.
(3,6) not a coprime.
(11,7) is a coprime. But since both 3 and 7 already belong to the same group, no extra grouping happened and we don't increment answer.

Same with (11,5),(11,2). No increment in answer.
(11,6) is a coprime. 11 belongs to g1 but 6 is not in g1 so adding 6 to g1 to form [3,11,7,5,2,6]. Increment answer.

Rest of the pairs does not increment answer as they all fall in the same group g1.

So answer is 5. Basically, trying to find the number of valid grouping operations or how many time grouping happened.

Note: If there is two pairs (113, 114), (23,45) such that {113, 23} belongs to group g1 as g1[113,23] and {114, 45} belongs to another group g2 as g2[114,45] then pair (113, 114) would group the two groups into one as g1[113,23,114,45] and hence no grouping would be performed for pair (23,45).

Currently, I am running two for loops to check all pairs and find the gcd to check if they are coprime. But this solution does not scale as the complexity is high O(n^2 log k).

Is there a better approach to solve this problem? Is Mobius function or Inclusion-exclusion principle be helpful here?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.