<p>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. </p>

<p>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)]$.</p>

CC BY-SA 3.0
2015-08-02T22:45:34.210Z
nice answer. please use \times not x to denote $Z_{p-1}\times Z_p$
kodlu
CC BY-SA 3.0
2015-08-02T11:23:34.670Z
2015-08-03T01:56:08.350Z
2015-08-03T01:56:08.350Z
user35014
<p>I would need a <a href="https://en.wikipedia.org/wiki/Sidon_sequence" rel="nofollow">Sidon sequence</a> 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.</p>

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

<p><strong>Extra</strong>: 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. </p>

<p>[1] Javier Cilleruelo, "Infinite Sidon sequences", eprint on arXiv: <a href="http://arxiv.org/abs/1209.0326" rel="nofollow">http://arxiv.org/abs/1209.0326</a></p>

CC BY-SA 3.0
2015-07-30T16:58:35.260Z
What density do you need?
Tyson Williams
CC BY-SA 3.0
2015-07-31T12:19:08.227Z
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.
chazisop
CC BY-SA 3.0
2015-07-31T14:30:25.503Z
I guess anything greater than $\sqrt{n}$ will do it
Cédric Van Rompay
<ds.algorithms>
Is there an efficient program for generating a Sidon sequence?
Cédric Van Rompay
# Is there an efficient program for generating a Sidon sequence?

(Asked by: username_0 on 2015-07-30)

I would need a [Sidon sequence](https://en.wikipedia.org/wiki/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>

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: What density do you need?  
> **username_2**: 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.  
> **username_0**: I guess anything greater than $\sqrt{n}$ will do it  

---

## 1 answers

### Answer by username_3 on 2015-08-02. Score: 4 | Accepted answer

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)]$.

> **Comments:**
> **username_4**: nice answer. please use \times not x to denote $Z_{p-1}\times Z_p$  

---

