Skip to main content
added 86 characters in body
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

A key observation is that two sets of generators $g, g'\subseteq [n]$ produce the same semigroup if and only if $\langle g\rangle \cap [n] = \langle g'\rangle \cap [n]$. Hence, the number of different semigroups equals the number of different $\langle g\rangle \cap [n]$ for $g\subseteq [n]$ (and this is what is computed in a naive way by the Sage code that I shared in the comments).

The question has an implicit restriction that the complement of $\langle g\rangle$ must be finite, which is equivalent to $g$ being set-wise coprime. Let's refer to the semigroups under this restriction as primitive and denote their number as $P(n)$. Without this restriction the semigroups (ie. both primitive and non-primitive) are enumerated by OEIS A103580. It is easy to see the following connection between the two counts: $${\tt A103580}(n) = \sum_{k=1}^n P(\lfloor \tfrac{n}{k}\rfloor ),$$ which implies that $P(n)$ can be obtained via Möbius inversion: $$P(n) = \sum_{k=1}^n \mu(k)\cdot {\tt A103580}(\lfloor \tfrac{n}{k}\rfloor ).$$ From 100 terms provided in the OEIS for A103580, we can immediately obtain $P(n)$ for $n\leq 100$.

Efficient computation of A103580 is discussed in the paper Counting numerical semigroups by Frobenius number, multiplicity, and depth by Sean Li (see Remark on page 12).

PS. I've added $P(n)$ to the OEIS as sequence A358392.

A key observation is that two sets of generators $g, g'\subseteq [n]$ produce the same semigroup if and only if $\langle g\rangle \cap [n] = \langle g'\rangle \cap [n]$. Hence, the number of different semigroups equals the number of different $\langle g\rangle \cap [n]$ for $g\subseteq [n]$ (and this is what is computed in a naive way by the Sage code that I shared in the comments).

The question has an implicit restriction that the complement of $\langle g\rangle$ must be finite, which is equivalent to $g$ being set-wise coprime. Let's refer to the semigroups under this restriction as primitive and denote their number as $P(n)$. Without this restriction the semigroups (ie. both primitive and non-primitive) are enumerated by OEIS A103580. It is easy to see the following connection between the two counts: $${\tt A103580}(n) = \sum_{k=1}^n P(\lfloor \tfrac{n}{k}\rfloor ),$$ which implies that $P(n)$ can be obtained via Möbius inversion: $$P(n) = \sum_{k=1}^n \mu(k)\cdot {\tt A103580}(\lfloor \tfrac{n}{k}\rfloor ).$$ From 100 terms provided in the OEIS for A103580, we can immediately obtain $P(n)$ for $n\leq 100$.

Efficient computation of A103580 is discussed in the paper Counting numerical semigroups by Frobenius number, multiplicity, and depth by Sean Li (see Remark on page 12).

A key observation is that two sets of generators $g, g'\subseteq [n]$ produce the same semigroup if and only if $\langle g\rangle \cap [n] = \langle g'\rangle \cap [n]$. Hence, the number of different semigroups equals the number of different $\langle g\rangle \cap [n]$ for $g\subseteq [n]$ (and this is what is computed in a naive way by the Sage code that I shared in the comments).

The question has an implicit restriction that the complement of $\langle g\rangle$ must be finite, which is equivalent to $g$ being set-wise coprime. Let's refer to the semigroups under this restriction as primitive and denote their number as $P(n)$. Without this restriction the semigroups (ie. both primitive and non-primitive) are enumerated by OEIS A103580. It is easy to see the following connection between the two counts: $${\tt A103580}(n) = \sum_{k=1}^n P(\lfloor \tfrac{n}{k}\rfloor ),$$ which implies that $P(n)$ can be obtained via Möbius inversion: $$P(n) = \sum_{k=1}^n \mu(k)\cdot {\tt A103580}(\lfloor \tfrac{n}{k}\rfloor ).$$ From 100 terms provided in the OEIS for A103580, we can immediately obtain $P(n)$ for $n\leq 100$.

Efficient computation of A103580 is discussed in the paper Counting numerical semigroups by Frobenius number, multiplicity, and depth by Sean Li (see Remark on page 12).

PS. I've added $P(n)$ to the OEIS as sequence A358392.

Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

A key observation is that two sets of generators $g, g'\subseteq [n]$ produce the same semigroup if and only if $\langle g\rangle \cap [n] = \langle g'\rangle \cap [n]$. Hence, the number of different semigroups equals the number of different $\langle g\rangle \cap [n]$ for $g\subseteq [n]$ (and this is what is computed in a naive way by the Sage code that I shared in the comments).

The question has an implicit restriction that the complement of $\langle g\rangle$ must be finite, which is equivalent to $g$ being set-wise coprime. Let's refer to the semigroups under this restriction as primitive and denote their number as $P(n)$. Without this restriction the semigroups (ie. both primitive and non-primitive) are enumerated by OEIS A103580. It is easy to see the following connection between the two counts: $${\tt A103580}(n) = \sum_{k=1}^n P(\lfloor \tfrac{n}{k}\rfloor ),$$ which implies that $P(n)$ can be obtained via Möbius inversion: $$P(n) = \sum_{k=1}^n \mu(k)\cdot {\tt A103580}(\lfloor \tfrac{n}{k}\rfloor ).$$ From 100 terms provided in the OEIS for A103580, we can immediately obtain $P(n)$ for $n\leq 100$.

Efficient computation of A103580 is discussed in the paper Counting numerical semigroups by Frobenius number, multiplicity, and depth by Sean Li (see Remark on page 12).