login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A164047 The number of symmetric numerical sets with odd Frobenius number and no small atoms. 1
1, 1, 2, 3, 6, 10, 20, 37, 73, 139, 275, 533, 1059, 2075, 4126, 8134, 16194, 32058, 63910, 126932, 253252, 503933, 1006056, 2004838, 4004124, 7987149, 15957964, 31854676, 63660327, 127141415, 254136782, 507750109 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Definition using terminology of [MM]: Asigma(k)' is the number of symmetric numerical sets S with Frobenius number 2k-1. This is denoted A^\sigma_{2k-1}^\prime in [MM]. Asigma(k)' equals the number of sigma-admissible subsets L of {1,2,...,2k-2} such that if x is an element of M then 2k-1-x is not an element of M. It also equals the number of vertices at height k in the rooted tree shown in figure 5 of [MM]. For large k, Asigma(k)' is approximately equal to .23065 x 2^(k-1) [MM]. The number of symmetric numerical sets with Frobenius number 2k and no small atoms equals Asigma(k)' by theorem 19 of [MM].

LINKS

Table of n, a(n) for n=1..32.

J. Marzuola and A. Miller, Counting Numerical Sets with No Small Atoms, arXiv:0805.3493 [math.CO], 2008.

J. Marzuola and A. Miller, Counting numerical sets with no small atoms, J. Combin. Theory A 117 (6) (2010) 650-667.

FORMULA

This theorem also provides a recursive connection with Asigma(k) from A158449: Asigma(2k+1)' = 2*Asigma(2k)' - Asigma(k).

PROG

(FORTRAN)

      program good

! This program calculates the cardinality of the number of symmetric numerical monoids without a small atom (or symmetric "good sets") for Frobenius number, $g$, as represented by $A_g^\sigma'$ defined in "Counting numerical sets with no small atoms" ([MM]) by Jeremy L. Marzuola and Andy Miller (to appear in Journal of Combinatorial Theory: A).

! Here we set the parameters of computation. We represent a numerical set by binary representations of the elements below the Frobenius number. Namely, a $0$ means an element is not in a set and a $1$ means an element is in the set. The symmetric numerical sets will be stored in an array called $Gin$, which will be redefined for each $g$ for the purposes of iterating the algorithm. Each row of Gin corresponds to a numerical set, e.g. the row $Gin(3, -)=(1, 1, 0, 1, 0, 0)$ would determine the numerical set ${1, 2, 4} \cup N_5$. This is a slight variation of the notation presented in Figure 5 of [MM], where only the initial half segment is presented since the remainder is clear by symmetry.

!The dimension here is limited only by the memory of the author's computers. With greater computational ability, you would be able to larger values of $g$.

!Generically we need only take the dimension of $z$ to be $Mit+3$.

      INTEGER*1, DIMENSION(21290000, 50) :: G1, Gin

      INTEGER, DIMENSION(40) :: z

      INTEGER j, Mit, N1, N2, k, n, flag1

!Initialize z to be zero in every component.

      do j = 1, 40 z(j) = 0 enddo

! $Mit$ is the number of times we iterate our algorithm. Since we begin with $g=3$, the resulting output will print out $A_g^\sigma'$ as $g$ ranges from $1$ to $Mit+3$. At each stage of the iteration, we have $g=j+3$.

      Mit = 24

! We begin with the symmetric good sets for $g=3$ given by only $(1, 0)$. We need these sets in order to run the algorithm suggested in the paper from the rooted tree in Figure 5 of [MM]. After each iteration of the code, $Gin$ will be redefined as the collection of symmetric good sets for $g = n+2$. If one wants to see the symmetric "good" sets for a specific $g$, one must print $Gin$ after the iteration leading to that $g$.

      Gin(1, 1) = 1

      Gin(1, 2) = 0

! We determine the number, $z(g)$, of symmetric good sets for $g = 1, 2, 3$ for the implementation of the algorithm. In the notation of [MM], $z(g) = A_g^\sigma'$.

      z(1) = 1

      z(2) = 1

      z(3) = 1

! $N1$ will represent the number of symmetric good sets $A_g^\sigma'$ for Frobenius number $g$ and $N2$ is the size of the numerical sets themselves for the given $g$. Here we begin with $g = 3$, so $N1 = A_3^\sigma' = 1$. For $g=n$, we have $N2 = |{1, ..., n-1}|=n-1$.

      N1 = 1

      N2 = 2

! Here we implement the algorithm by building the good sets for $g=2n+1$ based on those that exist for $g=2n-1$.

      do j = 1, Mit

        flag1 = 0

! If $g=2n$, we know from Theorem 19 of the paper that $z(2n)=z(2n-1)$.

        if (mod(j, 2) == 1) then

          z(j+3) = z(j+2)

        endif

! If $g=2n+1$, we implement the algorithm discussed in [MM]. Mainly, we need to count $A_g^\sigma'$. See Figure 5 for a pictoral reference to this algorithm.

        if (mod(j, 2) == 0) then

          do k = 1, N1

! Let $G$ be a symmetric good set for $g=2n-1$. If $G$ is bivalent, we can build good sets of size of size $2n+1$ by adding $01$, $10$ to the middle of the set as described in Figure 5 of [MM].

            if (maxval(Gin(k, 1:N2/2)-Gin(k, N2/2+1:N2)) > 0) then

              do n = 1, N2/2

                G1(flag1+1, n) = Gin(k, n)

                G1(flag1+2, n) = Gin(k, n)

                G1(flag1+1, N2/2+n+2) = Gin(k, N2/2+n)

                G1(flag1+2, N2/2+n+2) = Gin(k, N2/2+n)

              enddo

              G1(flag1+1, N2/2+1) = 1

              G1(flag1+2, N2/2+1) = 0

              G1(flag1+1, N2/2+2) = 0

              G1(flag1+2, N2/2+2) = 1

              flag1 = flag1+2

!erroneous? endif

            else

              do n = 1, N2/2

! If $G$ is not bivalent, we can build further good sets for $g=2n+1$ by adding $10$ to the middle of the set as described in Figure 5 of [MM].

                G1(flag1+1, n) = Gin(k, n)

                G1(flag1+1, N2/2+n+2) = Gin(k, N2/2+n)

              enddo

              G1(flag1+1, N2/2+1) = 1

              G1(flag1+1, N2/2+2) = 0

              flag1 = flag1+1

            endif

          enddo

          N1 = flag1

          N2 = 2+j

! Here we record the good sets, $Gin$, for the larger Frobenius number in order to move to the next stage of our algorithm.

          Gin(1:flag1, 1:N2) = G1(1:flag1, 1:N2)

! Here we record the number of good sets for $g=j+3$.

          z(j+3) = flag1

        endif

      enddo

! Here we print the total number of good symmetric numerical sets as output of the code for each of our computed Frobenius numbers.

      write(*, *) z

      end program

! Edited by M. F. Hasler, Jan 31 2020

CROSSREFS

Asigma(k)' is the same as the number of additive 2-bases for k-1 as described in A008929 and A066062. Related to Asigma(k) in A158449.

Sequence in context: A171682 A066062 A008929 * A158291 A045690 A007148

Adjacent sequences:  A164044 A164045 A164046 * A164048 A164049 A164050

KEYWORD

nonn

AUTHOR

Jeremy L. Marzuola (marzuola(AT)math.uni-bonn.de), Aug 08 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 17:09 EDT 2020. Contains 337321 sequences. (Running on oeis4.)