how many minimum possible co prime grouping upto $n$?

234 Views Asked by At

Suppose $n=5$. One co-prime grouping can be $\{(1,2),(3,4,5)\}$.

There can be any other combination, but the number of groups will be always $2$, i.e. $(1,2)$ and $(3,4,5)$.

Number of elements in a group can be minimum $2$.


Huge edit, so set off for inspection by OP.

Let $n$ be a positive integer. We say "$n$ makes us happy" when there is a partition of the integers $\{1, 2, \dots, n\}$ into two subsets, $p_1, p_2$ such that for all $x,y \in p_1$ with $x \neq y$, $\gcd(x,y) =1$, and similarly for distinct pairs of numbers in $p_2$.

What is the largest $n$ that makes us happy?

2

There are 2 best solutions below

1
On BEST ANSWER

Any such partition cannot have more than one even number in $p_1$ or in $p_2$, otherwise any two such even numbers are not coprime. So there are at most two even numbers in $\{1,2,\dots n\}$, which forces $n < 6$. You have given an example with $n = 5$, so $5$ is the largest number that makes us happy.

0
On

The question is not clear. I am interpreting it as asking: for each $n\in \mathbb n$ let $\Psi(n)$ denote the minimal number of subsets in a partition of $\{1,\cdots, n\}$ into disjoint subsets where the disjoint subsets are required to consist of relatively prime elements.

With my interpretation, we have $$\Psi(n)=\Big \lfloor \frac n2\Big \rfloor$$

To see that note that we need at least one subset for each even number. Thus $\Psi(n)≥\Big \lfloor \frac n2\Big \rfloor$

to get the opposite inequality, consider an odd prime $p$ and note that there are fewer than $\Big \lfloor \frac n2\Big \rfloor$ multiples of $p$ which are $≤n$, hence for each $p$ we can put $0$ or $1$ multiple of $p$ in each of the $\Big \lfloor \frac n2\Big \rfloor$ subsets. And we are done.