Problem Statement
Let $f(n)$ be the size of the largest subset $A\subseteq \{1,\ldots,n\}$ such that there are no three distinct elements $a,b,c\in A$ such that $a\mid b$ and $a\mid c$. How large can $f(n)$ be? Is $\lim f(n)/n$ irrational?
Categories:
Number Theory
Progress
The example $[m+1,3m+2]$ shows that $f(n)\geq\lceil \frac{2}{3}n\rceil$. Lebensold [Le76] has shown that, for large $n$,\[0.6725 n \leq f(n) \leq 0.6736 n.\]This is problem B24 in Guy's collection [Gu04].Source: erdosproblems.com/1062 | Last verified: January 19, 2026