amparvardi wrote: Consider the set of all strictly decreasing sequences of $n$ natural numbers having the property that in each sequence no term divides any other term of the sequence. Let $A = (a_j)$ and $B = (b_j)$ be any two such sequences. We say that $A$ precedes $B$ if for some $k$, $a_k < b_k$ and $a_i = b_i$ for $i < k$. Find the terms of the first sequence of the set under this ordering. Let $a_i$ such a sequence we know that $a_n\ne \frac {a_1}2$. If $a_n<\frac {a_1}2$, then : 1) $2a_n$ is not an element of the sequence 2) No element $a_k$ with $k<n$ divides $2a_n$ ($2a_n=\alpha a_k$ and $a_k>a_n$ would imply $\alpha <2$ and so $a_k=2a_n$, impossible). So we can create a new sequence, replacing $a_n$ with $2a_n$ and so we can find a sequence $b_k$ such that $b_1=a_1$ and $b_1< 2b_n$ So $2b_n>b_1\ge b_n+n-1$ and so $b_1>2n-2$ and so $b_1\ge 2n-1$ And since the sequence $2n-1, 2n-2, \ldots, n+1, n$ is a valid sequence, this is the first sequence of the set under the ordering.

So we define $A\prec B$ if for some $k$ we have $a_k < b_k$, with $a_i = b_i$ for all $1\leq i<k$, and we ask for the minimal $A_n$ such that $|A_n|=n$. Unfortunately this old solution from the above post is wrong. We know from the famous Erdös result that the largest subset $A$ of $\{1,2,\ldots,N\}$ such that no two elements of $A$ are in a divisibility relation has cardinality $|A| = \lceil N/2\rceil$. Therefore, for $|A| = n$, it follows $N \geq 2n-1$, and such a set can be $A = \{2n-1,2n-2,\ldots, n+1, n\}$, the one mentioned by pco. But (for $n>2$) $A' = \{2n-1, 2n-3,\ldots, n, n-1\}$ is also valid, and $A'\prec A$. Clearly, by the above, $\max A_n > 2n-2$, so $\boxed{\max A_n = 2n-1}$ (as the model shows). Clearly, for $n=1$ the minimal set is $A_1 = \{1\}$, while for $n=2$ the minimal set is $A_2 = \{3,2\}$. Simple casework, for larger values of $n$, yields $A_3=\{5,3,2\}$, $A_4=\{7, 5, 3, 2\}$, $A_5=\{9, 7, 6, 5, 4\}$, $A_6=\{11, 9, 7, 6, 5, 4\}$, $A_7 =\{13, 11, 9, 7, 6, 5, 4\}$, $A_8=\{15, 13, 11, 10, 9, 8, 7, 6\}$, etc. A much lesser-known result than the Erdös one mentioned above is the following Theorem (Abouabdillah). Consider the set $E = \{1,2,\ldots,2n\}$. An element $c\in E$ may belong to a subset $A\subset E$ with $n$ elements, such that for any two distinct elements of $A$ none divides the other, if and only if $c> n(2/3)^{k+1}$, where $k$ is the exponent of $2$ in the factorization of $c$. This theorem might be of some use in determining $A_n$, but based on the examples computed by hand I seriously doubt a complete answer may be garnered in the general case, other than, for $A_n$ given by $a_1 > a_2 > \cdots > a_n$, knowing $a_1 = 2n-1$, $a_2 = 2n-3$, and $a_k \geq 2(n-k) + 1$ for the remaining $3\leq k \leq n$. The related problem, where we define $A\prec B$ if for some $k$ we have $a_k < b_k$, with $a_i = b_i$ for all $k<i\leq n$ has a much simpler answer. Since in the context of the question there is no upper bound on the values of the elements of the sequence(s), clearly the minimal one is $A_n = \{p_n, p_{n-1}, \ldots, p_2,p_1=2\}$ (for $n>1$, as $A_1=\{1\}$ trivially), made of the first $n$ primes.