OPEN
This is open, and cannot be resolved with a finite computation.
Let $t\geq 1$ and $A\subseteq \{1,\ldots,N\}$ be such that whenever $a,b\in A$ with $b-a\geq t$ we have $b-a\nmid b$. How large can $\lvert A\rvert$ be? Is it true that\[\lvert A\rvert \leq \left(\frac{1}{2}+o_t(1)\right)N?\]
Asked by Erdős in a letter to Ruzsa in around 1980. Erdős observes that when $t=1$ the maximum possible is\[\lvert A\rvert=\left\lfloor\frac{N+1}{2}\right\rfloor,\]achieved by taking $A$ to be all odd numbers in $\{1,\ldots,N\}$. He also observes that when $t=2$ there exists such an $A$ with\[\lvert A\rvert \geq \frac{N}{2}+c\log N\]for some constant $c>0$: take $A$ to be the union of all odd numbers together with numbers of the shape $2^k$ with $k$ odd.
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 #635, https://www.erdosproblems.com/635, accessed 2026-01-16
