Problem #334: Find the best function $f(n)$ such that every $n$ can be...

---

Progress

Erdős originally asked if even $f(n)\leq n^{1/3}$ is true. This is known, and the best bound is due to Balog [Ba89] who proved that\[f(n) \ll_\epsilon n^{\frac{4}{9\sqrt{e}}+\epsilon}\]for all $\epsilon>0$. (Note $\frac{4}{9\sqrt{e}}=0.2695\ldots$.)

It is likely that $f(n)\leq n^{o(1)}$, or even $f(n)\leq e^{O(\sqrt{\log n})}$.

See also Problem 59 on Green's open problems list.