Problem Statement
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$?
Categories:
Number Theory Additive Combinatorics Sidon Sets
Progress
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].
Source: erdosproblems.com/340 | Last verified: January 14, 2026