Minimum # of subsets in partition $\{2, 3, 4..., 2^n\}$ so that every subset contain only numbers that are not multiples of each other.

Question

Example: if $X = \{2,3,4,...,16\}$ then, subsets are $A=\{2,3,5,7,11,13\}$ , $B=\{4,6,9,10,14,15\}$ , $C=\{8,12\}$ and D=$\{16\}$.

I notice that for $2^n$ consecutive elements I'll have $n$ subsets because every $2^nth$ element always needs new partition subset, but I can't figure out how to prove it.

Answer 1

$2^1, 2^2, 2^3, \dots, 2^n$ must all be in different subsets, so we need at least $n$.

If we break up into intervals, taking the $k^{\text{th}}$ subset to be $\{2^k, 2^k + 1, 2^k + 2, \dots, 2^{k+1}-1\}$, we get a solution with $n$ subsets for all $n$.