OPEN
This is open, and cannot be resolved with a finite computation.
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\[\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2-\epsilon}\]for all $\epsilon>0$ and large $N$?
This sequence is sometimes called the Mian-Chowla sequence. It is trivial that this sequence grows at least like $\gg N^{1/3}$.
Erdős and Graham
[ErGr80] also asked about the difference set $A-A$, whether this has positive density, and whether this contains $22$. It does contain $22$, since $a_{15}-a_{14}=204-182=22$. The smallest integer which is unknown to be in $A-A$ is $33$ (see
A080200). It may be true that all or almost all integers are in $A-A$.
This sequence is at
OEIS A005282.
See also
[156].
View the LaTeX source
This page was last edited 18 November 2025.
Additional thanks to: Boris Alexeev and Vjekoslav Kovac
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 #340, https://www.erdosproblems.com/340, accessed 2026-01-16
