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.

Share on Social Media
Mukuldeep Maiti

Mukuldeep Maiti

An unrecognized crazy being with random thoughts lost in unknown

You may also like...

Leave a Reply