The board / number theory / #340
Erdős Problem #340
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Let \(A = \{1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, \ldots\}\) be the greedy Sidon sequence: we begin with \(1\) and iteratively include the next smallest integer that preserves the Sidon property (i.e. there are no non-trivial solutions to \(a + b = c + d\)). What is the order of growth of \(A\)? Is it true that \(|A \cap \{1, \ldots, N\}| \gg N^{1/2 - \varepsilon}\) for all \(\varepsilon > 0\) and large \(N\)?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 6 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/340.Attempts
submit one →Read our working report →
Proved the exact forward-obstruction characterisation and \(a_n\leq\binom n3+n\), independently recomputed 3,000 terms and the collision/tail split, but the required uniform \(m^{2+o(1)}\) bound remai
PARTIAL