OFFSET
0,2
COMMENTS
The semigroup analog of A005432.
We apply the categorical viewpoint and consider the empty set as a semigroup.
The first 4 terms can be calculated by brute force search (see attached program).
LINKS
James East, Attila Egri-Nagy, James D. Mitchell, Enumerating Transformation Semigroups, Semigroup Forum 95, 109-125 (2017); arXiv: 1403.0274 [math.GR], 2014-2017.
PROG
(GAP)
################################################################################
# GAP 4.5 function implementing a brute force search for submagmas of a magma.
# (C) 2012 Attila Egri-Nagy www.egri-nagy.hu
# GAP can be obtained from www.gap-system.org
################################################################################
# The function goes through all the subsets of the given magma (groups,
# semigroups) and checks whether they form a magma or not.
# If yes, then the submagma is collected.
# The function returns the list of all (nonempty) submagmas.
BruteForceSubMagmaSearch := function(M)
local bitlist, #the characteristic function of a subset
i, #an integer to index through the bitlist
n, #size of the input magma
elms, #elements of the magma
gens, #generator set of a submagma
submagmas, #the submagmas
duplicates, #for counting how many times we encounter the same submagma
nonsubmagmas; #counting how many subsets are not submagmas
# duplicates + nonsubmagmas = 2^n-1
n := Size(M);
submagmas := [];
elms := AsList(M);
duplicates := 0;
nonsubmagmas := 0;
bitlist := BlistList([1..n], [1]); #we start with the first element, the
#empty set can be added afterwards, if the magma's definition allows it
repeat
#constructing a generator set based on the bitlist##########################
gens := [];
Perform([1..n], function(x) if bitlist[x] then Add(gens, elms[x]); fi; end);
#checking whether it is a submagma
if Size(gens) = Size(Magma(gens)) then
if gens in submagmas then
duplicates := duplicates + 1;
else
AddSet(submagmas, gens);
fi;
else
nonsubmagmas := nonsubmagmas + 1;
fi;
#binary +1 applied to bitlist###############################################
i := 1;
while (i<=n) and (bitlist[i]) do
bitlist[i] := false;
i := i + 1;
od;
if i <= n then bitlist[i] := true; fi;
############################################################################
until SizeBlist(bitlist) = 0;
Print("#I Submagmas:", Size(submagmas),
" Duplicates:", duplicates,
" Nonsubmagmas:", nonsubmagmas, "\n");
return submagmas;
end;
CROSSREFS
KEYWORD
nonn,hard,more,nice
AUTHOR
Attila Egri-Nagy, Aug 19 2012
EXTENSIONS
a(4) moved from comments to data by Andrey Zabolotskiy, Mar 25 2021
STATUS
approved