login
The OEIS is supported by the many generous donors to the OEIS 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. 4
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, 1015059238, 2028564292, 4055812657, 8107052520 (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
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 A008929 A066062 * A158291 A045690 A007148
KEYWORD
nonn
AUTHOR
Jeremy L. Marzuola (marzuola(AT)math.uni-bonn.de), Aug 08 2009
EXTENSIONS
a(33) onwards from Martin Fuller, Sep 13 2023
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 09:32 EDT 2024. Contains 371268 sequences. (Running on oeis4.)