Divide first n natural number into minimum number of co-prime subsets

It is to divide the first n natural number into the minimum number of subsets such that each element is pairwise co-prime with every other element from the subset.

Let’s move towards the solution, subsets will have elements whose pairwise gcd is 1, i.e. no two elements will have a common factor, which implies, multiples of some number will be in different subsets. For example, multiple of 2 i.e. 2,4,6,8,10,….. each will be in different subsets, multiples of 3 i.e. 3,6,9,12…. will be in different subsets, etc. For any given n, the maximum number of multiples less than n will of multiples of 2. So, the minimum number of subsets, can be formed that contains pairwise co-prime numbers will be the number of multiples of 2 less than equal to n, that is (integer) n/2.

Now, forming each subset. As each adjacent pair of natural numbers is co-prime and each adjacent pair of odd numbers is co-prime, each odd number can be placed with its adjacent even number. 1 can be placed in any subset as it is co-prime with any other number.

Have a look for some value of n,

For n=1, minimum number of subset is 1, subsets is {1}.
For n=2, minimum number of subset is 1, subsets is {1,2}.
For n=3, minimum number of subset is 1, subsets is {1,2,3}.
For n=4, minimum number of subset is 2, subsets is {1,2},{3,4}.
For n=5, minimum number of subset is 2, subsets is {1,2,5},{3,4}.
For n=6, minimum number of subset is 3, subsets is {1,2},{3,4},{5,6}.
For n=7, minimum number of subset is 3, subsets is {1,2,7},{3,4},{5,6}.
For n=8, minimum number of subset is 4, subsets is {1,2},{3,4},{5,6},{7,8}.
For n=9, minimum number of subset is 4, subsets is {1,2,9},{3,4},{5,6},{7,8}.

C++ implementation is given below

#include<bits/stdc++.h>
using namespace std;
int main()
{
  	long n,k;
    cout<<"enter n:";
    cin>>n;
    if(n==1){
        cout<<"minimum number of subset: "<<1<<endl;
      	cout<<"subsets: ";
        cout<<"{1} "<<endl;
    }else {
        k=n/2;
        cout<<"minimum number of subset: "<<k<<endl;
        cout<<"subsets: ";
        if (n & 1) {//if n is odd
            cout<<"{1 2 "<<n<<"} "<<endl;
        } else {//if n is even
            cout<<"{1 2}"<<endl;
        }
        for (int i=3;i<n;i+=2) {
            cout<<"{"<<i<<" " <<i+1<<"} "<< endl;
        }
    }
    return 0;
}

Donot hesitate to ping me in the comment section below.

Mukuldeep Maiti

Mukuldeep Maiti

An unrecognized crazy being with random thoughts lost in unknown

You may also like...

Leave a Reply