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].
Additional thanks to: Boris Alexeev and Vjekoslav Kovac
