# Is there an efficient program for generating a Sidon sequence?

I would need a Sidon sequence of about $10^9$ elements. I found math papers like [1] that explain how to generate Sidon sequences but it seems a lot of pain to write the corresponding program.

Are you aware of any existing program that generates a dense enough and large enough Sidon sequence ?

Extra: my real constraint for the sequence is $a+a′ , a \lt a′ ,~ a,a′ ∈ A$ instead of the true Sidon sequence property $a+a ′ , a ≤ a ′ , a, a ′ ∈ A$. So a Sidon sequence would do the job but I could hope for a denser sequence by tuning the program.

[1] Javier Cilleruelo, "Infinite Sidon sequences", eprint on arXiv: http://arxiv.org/abs/1209.0326

• What density do you need? Jul 30, 2015 at 16:58
• If you need a finite Sidon set there are explicit methods that provides Sidon sets in [1,n] of size sqrt n.
– user34987
Jul 30, 2015 at 18:41
• I believe your answer could be vastly improved if you could provide a source or in general any further informations on these methods. Also note that the question restricts the search to an existing program or one could assume, an easily programmable method. Jul 31, 2015 at 12:19
• I guess anything greater than $\sqrt{n}$ will do it Jul 31, 2015 at 14:30

Consider a prime $p$ and let $g$ be a primitive root mod $p$. The set $A= \{ (x,g^{x}), x=0,..,p-2\}$ is a Sidon set in $Z_{p-1} \times Z_{p}$. This is an explicit method.
Now, since $Z_{p-1} \times Z_{p}$ is isomorphic to $Z_{p(p-1)}$, then the natural isomorphism $\Phi$ maps $A$ in $\Phi(A)$, which is also a Sidon set in $Z_{p(p-1)}$, which is a Sidon set in $[1,p(p-1)]$.
• nice answer. please use \times not x to denote $Z_{p-1}\times Z_p$ Aug 2, 2015 at 22:45