cp's OEIS Frontend

A164047 The number of symmetric numerical sets with odd Frobenius number and no small atoms.

%I A164047 #22 Sep 13 2023 08:35:36
%S A164047 1,1,2,3,6,10,20,37,73,139,275,533,1059,2075,4126,8134,16194,32058,
%T A164047 63910,126932,253252,503933,1006056,2004838,4004124,7987149,15957964,
%U A164047 31854676,63660327,127141415,254136782,507750109,1015059238,2028564292,4055812657,8107052520
%N A164047 The number of symmetric numerical sets with odd Frobenius number and no small atoms.
%C A164047 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].
%H A164047 Martin Fuller, <a href="/A164047/b164047.txt">Table of n, a(n) for n = 1..66</a>
%H A164047 J. Marzuola and A. Miller, <a href="http://arxiv.org/abs/0805.3493">Counting Numerical Sets with No Small Atoms</a>, arXiv:0805.3493 [math.CO], 2008.
%H A164047 J. Marzuola and A. Miller, <a href="https://doi.org/10.1016/j.jcta.2010.03.002">Counting numerical sets with no small atoms</a>, J. Combin. Theory A 117 (6) (2010) 650-667.
%F A164047 This theorem also provides a recursive connection with Asigma(k) from A158449: Asigma(2k+1)' = 2*Asigma(2k)' - Asigma(k).
%o A164047 (FORTRAN)
%o A164047       program good
%o A164047 ! 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).
%o A164047 ! 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.
%o A164047 !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$.
%o A164047 !Generically we need only take the dimension of $z$ to be $Mit+3$.
%o A164047       INTEGER*1, DIMENSION(21290000,50) :: G1, Gin
%o A164047       INTEGER, DIMENSION(40) :: z
%o A164047       INTEGER j, Mit, N1, N2, k, n, flag1
%o A164047 !Initialize z to be zero in every component.
%o A164047       do j = 1,40 z(j) = 0 enddo
%o A164047 ! $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$.
%o A164047       Mit = 24
%o A164047 ! 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$.
%o A164047       Gin(1,1) = 1
%o A164047       Gin(1,2) = 0
%o A164047 ! 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'$.
%o A164047       z(1) = 1
%o A164047       z(2) = 1
%o A164047       z(3) = 1
%o A164047 ! $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$.
%o A164047       N1 = 1
%o A164047       N2 = 2
%o A164047 ! Here we implement the algorithm by building the good sets for $g=2n+1$ based on those that exist for $g=2n-1$.
%o A164047       do j = 1,Mit
%o A164047         flag1 = 0
%o A164047 ! If $g=2n$, we know from Theorem 19 of the paper that $z(2n)=z(2n-1)$.
%o A164047         if (mod(j,2) == 1) then
%o A164047           z(j+3) = z(j+2)
%o A164047         endif
%o A164047 ! 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.
%o A164047         if (mod(j,2) == 0) then
%o A164047           do k = 1,N1
%o A164047 ! 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].
%o A164047             if (maxval(Gin(k,1:N2/2)-Gin(k,N2/2+1:N2)) > 0) then
%o A164047               do n = 1,N2/2
%o A164047                 G1(flag1+1,n) = Gin(k,n)
%o A164047                 G1(flag1+2,n) = Gin(k,n)
%o A164047                 G1(flag1+1,N2/2+n+2) = Gin(k,N2/2+n)
%o A164047                 G1(flag1+2,N2/2+n+2) = Gin(k,N2/2+n)
%o A164047               enddo
%o A164047               G1(flag1+1,N2/2+1) = 1
%o A164047               G1(flag1+2,N2/2+1) = 0
%o A164047               G1(flag1+1,N2/2+2) = 0
%o A164047               G1(flag1+2,N2/2+2) = 1
%o A164047               flag1 = flag1+2
%o A164047 !erroneous? endif
%o A164047             else
%o A164047               do n = 1,N2/2
%o A164047 ! 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].
%o A164047                 G1(flag1+1,n) = Gin(k,n)
%o A164047                 G1(flag1+1,N2/2+n+2) = Gin(k,N2/2+n)
%o A164047               enddo
%o A164047               G1(flag1+1,N2/2+1) = 1
%o A164047               G1(flag1+1,N2/2+2) = 0
%o A164047               flag1 = flag1+1
%o A164047             endif
%o A164047           enddo
%o A164047           N1 = flag1
%o A164047           N2 = 2+j
%o A164047 ! Here we record the good sets, $Gin$, for the larger Frobenius number in order to move to the next stage of our algorithm.
%o A164047           Gin(1:flag1,1:N2) = G1(1:flag1,1:N2)
%o A164047 ! Here we record the number of good sets for $g=j+3$.
%o A164047           z(j+3) = flag1
%o A164047         endif
%o A164047       enddo
%o A164047 ! Here we print the total number of good symmetric numerical sets as output of the code for each of our computed Frobenius numbers.
%o A164047       write(*,*) z
%o A164047       end program
%o A164047 ! Edited by _M. F. Hasler_, Jan 31 2020
%Y A164047 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.
%K A164047 nonn
%O A164047 1,3
%A A164047 Jeremy L. Marzuola (marzuola(AT)math.uni-bonn.de), Aug 08 2009
%E A164047 a(33) onwards from _Martin Fuller_, Sep 13 2023