Problem Statement
Let $f(n)$ be minimal such that $\{1,\ldots,n-1\}$ can be partitioned into $f(n)$ classes so that $n$ cannot be expressed as a sum of distinct elements from the same class. How fast does $f(n)$ grow?
Categories:
Number Theory
Progress
Alon and Erdős [AlEr96] proved that $f(n) = n^{1/3+o(1)}$, and more precisely\[\frac{n^{1/3}}{(\log n)^{4/3}}\ll f(n) \ll \frac{n^{1/3}}{(\log n)^{1/3}}(\log\log n)^{1/3}.\]Vu [Vu07] improved the lower bound to\[f(n) \gg \frac{n^{1/3}}{\log n}.\]Conlon, Fox, and Pham [CFP21] determined the order of growth of $f(n)$ up to a multiplicative constant, proving\[f(n) \asymp \frac{n^{1/3}(n/\phi(n))}{(\log n)^{1/3}(\log\log n)^{2/3}}.\]Source: erdosproblems.com/360 | Last verified: January 14, 2026