In the mathoverflow question here the asymptotic growth of antichains in the divisibility poset ${\cal P}_n$ of the set of natural numbers $\{1,\ldots,n\}$ is considered. I have a somewhat dual question.

Consider a ``packing'' of disjoint singly generated ideals (upsets) ${\cal C}_x$ where $${\cal C}_x=\{x,y_1 x, y_1 y_2 x, \ldots \} \in \{1,2,\ldots,n\}$$ with $y_i$ natural numbers greater than 1. To be precise, an ideal $\cal C$ is a collection of sets such that if $A\in {\cal C}$ and $A \subset B$ we have $B \in {\cal C}$. I consider only ideals generated by a single integer $x,$ which I call ${\cal C}_x$ and I consider only the integers $\{1,\ldots,n\}$ not the whole set of natural numbers.

Thus, $x$ is the minimal element in the ideal ${\cal C}_x$ and I require that ${\cal C}_{x'}\cap {\cal C}_x=\emptyset$ whenever $x \neq x'.$ The cost of an ideal ${\cal C}_x$ is simply

$f({\cal C}_x)=1/x $

where $x$ is its minimal element. I want to find a collection of disjoint ideals ${\cal M}=\{C_{x_1},\ldots,C_{x_m}\}$ which **maximizes** the cost $$f({\cal M})=\sum_{i=1}^m f(C_{x_i})=\sum_{i=1}^m \frac{1}{x_i}$$ for large $n$.

**Edit 1:** There is a side condition to the maximization, which I forgot to write, sorry. To be able to include both $x\neq x'$ in $\cal M$ they must not divide each other in addition to their LCM being strictly greater than $n$.

**Edit 2:** It seems to me the condition in Edit 1 is superfluous, since if $LCM(x,x')$ is strictly larger than $n$ the condition of either of $x,x'$ not dividing the other is automatically satisfied. However, subsets of $\{1,\ldots,n\}$ where no element of the subset divides another have been investigated for a long time, under the terminology ``primitive sets''. So I suppose I am asking about how small can $f({\cal M})$ be, in comparison to primitive sets which achieve $f$ of $O\left(\frac{\log n}{\sqrt{\log \log n}}\right)$

An upper bound of $\lceil \frac{n+1}{2}\rceil$ is known on the **size** of a collection obeying this LCM condition, see this previous MO question here.
However, the size maximizing sets that are easy to find are essentially mostly integers from $[n/2,n]$ and the value of $f$ they give is constant (since it is $H_n-H_{n/2}$). However, it is known that for so called **primitive sets** in $\{1,\ldots,n\}$ considered by Behrend, Erdos and others (sets of integers satisfying the non-divisibility conditions) the value of $f$ is proved to be asymptotically $\frac{\log n}{\sqrt{\log \log n}}$.

It seems like some pruning of primitive sets by removing their members in $[2,\sqrt{n+1})\cap \mathbb{N}$ and pruning multiples of small primes we should get a collection with cost $f$ possibly not much lower than primitive sets.

chosenso that $C_x\cap C_{x'}=\varnothing$, or it is our constraint to choose $x_1,x_2,\dots$ so that the resulting sets are disjoint? $\endgroup$ – Ilya Bogdanov Nov 27 '15 at 6:54