OPEN
This is open, and cannot be resolved with a finite computation.
Let $F(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain any set of the form $\{n,2n,3n\}$. What is\[ \lim_{N\to \infty}\frac{F(N)}{N}?\]Is this limit irrational?
This limit was proved to exist by Graham, Spencer, and Witsenhausen
[GSW77], who showed it is equal to\[\frac{1}{3}\sum_{k\in K}\frac{1}{d_k},\]where $d_1<d_2<\cdots $are the $3$-smooth numbers and $K$ is the set of $k$ for which $f(k)>f(k-1)$, where $f$ counts the largest subset of $\{d_1,\ldots,d_k\}$ that avoids $\{n,2n,3n\}$.
Similar questions can be asked for the density or upper density of infinite sets without such configurations.
The limit can be estimated by elementary arguments (see the comments). Eberhard has used the formula of
[GSW77] mentioned above to calculate the value of the limit as\[0.800965\cdots.\]This problem has been
formalised in Lean as part of the
Google DeepMind Formal Conjectures project.
View the LaTeX source
This page was last edited 24 October 2025.
Additional thanks to: Sarosh Adenwalla, Boris Alexeev, Stijn Cambie, Jonathan Chapman, and Sean Eberhard
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #168, https://www.erdosproblems.com/168, accessed 2026-01-16
