Problem Statement
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?
Categories:
Additive Combinatorics
Progress
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.
Source: erdosproblems.com/168 | Last verified: January 13, 2026