Set of natural numbers related to least common multiple I have come across the following set in my research, and I am curious whether this has been studied before/if there is a reference for a related construction.
Given a natural number $n$, let $S(n)$ be the largest subset of $\{1,\dots, n\}$ such that no element is a multiple of another, if multiple sets exist, choose the one with largest elements. For example, $S(5)=\{3,4,5\}$, $S(6)=\{4,5, 6\}$.
Intuitively, this set seems somehow related to the concept of least common multiples and prime factorizations, and I am very curious if anyone has any pointers to where this may have come up before.
 A: The number of odd numbers in $\{1,2,\ldots,n\}$ is $\left\lfloor\frac{n+1}{2}\right\rfloor$, and that number (call it $s(n)$) is the size of a maximal subset of $\{1,2,\ldots,n\}$ which has no two elements such that one is a multiple of another.
Proof: On one hand, $\{n-s(n)+1, n-s(n)+2,\ldots, n\}$ is a subset of $s(n)$ numbers such that no number from it divides another. This is because they are "too big". A multiple, even of the smallest of them: $n-s(n)+1$ would already be at least a double of it, i.e.
$$\begin{array}{rcl}2(n-s(n)+1)&=&2n-2\left\lfloor\frac{n+1}{2}\right\rfloor+2\\&\ge& 2n-2\frac{n+1}{2}+2\\&=&2n-(n+1)+2\\&=&n+1\\&>&n\end{array}$$
which is too big to also be in the set.
On the other hand, let's suppose you've got a subset $U\subset\{1,2,\ldots,n\}$ such that no number in $U$ divides another. "Reduce" each number from $U$ by repeatedly dividing by $2$ until you get an odd number. We claim that any two different numbers in $U$ "reduce" to two different odd numbers. Namely, if $x,y\in U, x\ne y$ and they both "reduce" to the same odd number $z$, then it would mean that $x=2^iz, y=2^jz$ and then either $x\mid y$ (if $i<j$) or $y\mid x$ (if $j<i$). That means there is a $1-1$ (may not be "onto") map from $U$ to the set of all odd numbers in $\{1,2,\ldots, n\}$. This further means that $U$ has at most $s(n)$ elements.
Finally, this proof produces a subset of the exact size $s(n)$ which is maximal in terms of the size of the elements, namely the above set $\{n-s(n)+1, n-s(n)+2,\ldots, n\}$, which then deserves to be called $S(n)$.$\,\blacksquare$
