Sidon sets and their generalizations, Sidon \(g\)-sets

AUTHORS:

  • Martin Raum (07-25-2011)
sage.combinat.sidon_sets.sidon_sets(N, g=1)

Return the set of all Sidon-\(g\) sets that have elements less than or equal to \(N\).

A Sidon-\(g\) set is a set of positive integers \(A \subset [1, N]\) such that any integer \(M\) can be obtain at most \(g\) times as sums of unordered pairs of elements of \(A\) (the two elements are not necessary distinct):

\[\#\{ (a_i, a_j) | a_i, a_j \in A, a_i + a_j = M,a_i \leq a_j \} \leq g\]

INPUT:

  • \(N\) – A positive integer.
  • \(g\) – A positive integer (default: \(1\)).

OUTPUT:

  • A Sage set with categories whose element are also set of integers.

EXAMPLES:

sage: S = sidon_sets(3, 2)
sage: sorted(S, key=str)
[{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2, 3}, {2}, {3}, {}]
sage: S.cardinality()
8
sage: S.category()
Category of finite sets
sage: sid = S.an_element()
sage: sid
{2}
sage: sid.category()
Category of finite sets
sage.combinat.sidon_sets.sidon_sets_rec(N, g=1)

Return the set of all Sidon-\(g\) sets that have elements less than or equal to \(N\) without checking the arguments. This internal function should not be call directly by user.