I'm trying to solve the following problem: given an integer $n$, under which conditions of $n$ the following statement is true:
For any $1 < k \leq n$, there is always a partition of $k$ parts of $n$ so that each part is coprime with $n$.
Here is what I obtained:
- The statement is obviously true if $n$ is prime,
- If $n > 2$ then $n$ is odd since $2$ must occur in the partition of $n-1$ part of $n$.
I think that the condition should be:
$n$ is either $2$ or an odd number.
I've tried several numbers, for example $9$ (the first odd number which is not prime):
$$\begin{align*}9 &= 1 + \dots + 1 \\ &= \dots \\ &= 1 + 4 + 4 \\ &= 1 + 8 \end{align*}$$
Using the trick of grouping powers of $2$, I've found that if $n = (a_1 \dots a_i)_{m}$ for some base $m$ where $gcd(m,n) = 1$, then there is always a partition of $k$ part where $\sum\limits_{j=1}^{i} a_j \leq k \leq n$. Then I found that $15$, $21$ are ok too.
For example:
- $15 = 1111_2$, so I can find partition until $1+1+1+1 = 4$ parts, and
- $15 = 21_7$, so I can find partition until $2+1 = 3$ parts, finally
- $15 = 11_{14}$, so I can find partition until $1+1= 2$ parts.
and:
- $21 = 10101_{2}$, so until $3$,
- $21 = 11_{20}$, so until $2$.
Let $n$ be an odd integer and let $m$ be the largest positive integer with $2^m<n$, then $\gcd(n,n-2^m)=\gcd(n,2^m)=1$. Now, for $0\le \ell\le m$, $$ n =(n-2^m) +2^{m-\ell}+ \sum_{i=0}^\ell2^{m-i}, $$ which shows the partitions exist for $2\le k\le m+3$. Because the number of digits in the binary representation of $n$ equal to $1$ is at most $m$, your grouping of powers of $2$ trick works for all other values of $k$.