Dual View Random Solved Random Open
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.\]
Additional thanks to: Sarosh Adenwalla, Boris Alexeev, Stijn Cambie, Jonathan Chapman, and Sean Eberhard
Proof expositions (0)
If you would like to contribute an exposition of a proof related to this problem, please message a moderator or leave your exposition as a comment.

No proof expositions yet.
Comments (9) Proof claims (0)
More information and links
This page was last edited 23 March 2026. (View history) (View the LaTeX source)

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-09-01

From the external database. (You can help update this.)
Formalised statement? Yes
Reactions
Likes apiros3
Open to collaboration lezhe
Currently working on None
Looks difficult None
Looks tractable None
Could be formalisable None
Working on formalising None