OPEN
This is open, and cannot be resolved with a finite computation.
Let $1=a_1<a_2<\cdots$ be the sequence of integers defined by $a_1=1$ and $a_{k+1}$ is the smallest integer $n$ for which the number of solutions to $a_i+a_j \leq n$ (with $i\leq j\leq k$) is less than $n-k$.
Is the number of solutions to $a_i+a_j \leq x$ equal to $x+O(x^{1/4+o(1)})$?
This sequence was constructed by Rosen. Note that the number of solutions to $a_i+a_j\leq x$ is always at least $x$ by construction. Erdős and Rosen could not even prove whether the number of solutions to $a_i+a_j\leq x$ satisfies is at most $(1+o(1))x$.
The sequence begins\[1,3,5,9,13,17,24,31,38,45,\ldots.\]
View the LaTeX source
This page was last edited 16 November 2025.
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 #954, https://www.erdosproblems.com/954, accessed 2026-01-16
