2
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ What density do you need? $\endgroup$
    – Tyson Williams
    Jul 30, 2015 at 16:58
  • $\begingroup$ If you need a finite Sidon set there are explicit methods that provides Sidon sets in [1,n] of size sqrt n. $\endgroup$
    – user34987
    Jul 30, 2015 at 18:41
  • $\begingroup$ 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. $\endgroup$
    – chazisop
    Jul 31, 2015 at 12:19
  • $\begingroup$ I guess anything greater than $\sqrt{n}$ will do it $\endgroup$
    – Cédric Van Rompay
    Jul 31, 2015 at 14:30

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ nice answer. please use \times not x to denote $Z_{p-1}\times Z_p$ $\endgroup$
    – kodlu
    Aug 2, 2015 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.