|
#############################################################################
##
#W arf-med.gi Manuel Delgado <mdelgado@fc.up.pt>
#W Pedro A. Garcia-Sanchez <pedro@ugr.es>
#W Jose Morais <josejoao@fc.up.pt>
##
##
#Y Copyright 2005 by Manuel Delgado,
#Y Pedro Garcia-Sanchez and Jose Joao Morais
#Y We adopt the copyright regulations of GAP as detailed in the
#Y copyright notice in the GAP manual.
##
#############################################################################
#####################################################################
## ARF
## See [RGGB04]
#####################################################################
##
#F ArfNumericalSemigroupClosure(arg)
##
## The argument may be a numerical semigroup or a list of relatively prime
## positive integers
## The output is the Arf-closure of arg (the smallest Arf-semigroup
## containing arg)
##
#####################################################################
InstallGlobalFunction(ArfNumericalSemigroupClosure, function(arg)
local set, min, A, i, MIN, small, ac;
if Length(arg) = 1 and IsNumericalSemigroup(arg[1]) then
if HasMinimalGeneratingSystemOfNumericalSemigroup(arg[1]) then
set := MinimalGeneratingSystemOfNumericalSemigroup(arg[1]);
else
set := GeneratorsOfNumericalSemigroup(arg[1]);
fi;
elif Length(arg) = 1 then
if Gcd(arg[1]) <> 1 then
Error("The greatest common divisor is not 1");
fi;
set := arg[1];
else
if Gcd(arg) <> 1 then
Error("The greatest common divisor is not 1");
fi;
set := arg;
fi;
set := Set(set);
min := Minimum(set);
if min <= 0 then
Error("The elements of the list must be positive integers");
fi;
A := [set];
i := 1;
while true do
if (1 in A[i]) then
MIN := List(A, x -> Minimum(x));
small := List([0..Length(MIN)], i -> Sum(MIN{[1..i]}));
ac:=NumericalSemigroupBySmallElements(small);
Setter(IsArfNumericalSemigroup)(ac,true);
return ac;
fi;
A[i+1] := Union([min],Difference(Set(A[i], x -> x-min),[0]));
i := i+1;
min := Minimum(A[i]);
od;
end);
InstallMethod(ArfClosure,
"Computes the Arf closure of a numerical semigroup",
[IsNumericalSemigroup],
ArfNumericalSemigroupClosure
);
#####################################################################
##
#P IsArfNumericalSemigroup(s)
##
## The argument s is a numerical semigroup
## returns true if s is an Arf-semigroup and false otherwise
##
#####################################################################
InstallMethod(IsArfNumericalSemigroup,
"Tests if a Numerical Semigroup is an Arf-semigroup",
[IsNumericalSemigroup],
function(s)
return (s = ArfNumericalSemigroupClosure(s));
end);
InstallTrueMethod(IsMEDNumericalSemigroup,IsArfNumericalSemigroup);
InstallTrueMethod(IsAcuteNumericalSemigroup,IsArfNumericalSemigroup);
#####################################################################
##
#A MinimalArfGeneratingSystemOfArfNumericalSemigroup(s)
##
## The argument s is an Arf numerical semigroup
## returns the minimal Arf-generating system of s.
## Implemented with G. Zito
#############################################################################
InstallMethod(MinimalArfGeneratingSystemOfArfNumericalSemigroup,
"Returns the minimal Arf-generating system of an Arf-semigroup",
[IsNumericalSemigroup],
function(s)
local char, ms,i,j, m, r, b;
if not(IsArfNumericalSemigroup(s)) then
Error("The argument must be an Arf numerical semigroup");
fi;
ms:=Concatenation(MultiplicitySequenceOfNumericalSemigroup(s),[1]);
r:=List(ms,_->0);
for i in [1..Length(ms)] do
b:=First([i+1..Length(ms)], j->ms[i]=Sum(ms{[i+1..j]}));
if b=fail then
b:=Length(ms);
fi;
for j in [i+1..b] do
r[j]:=r[j]+1;
od;
od;
i:=Filtered([1..Length(ms)-1], j->r[j]<r[j+1]);
return List(i, j->Sum(ms{[1..j]}));
end);
#####################################################################
##
#F ArfNumericalSemigroupsWithFrobeniusNumber(f)
##
## The argument f is an integer
## Returns the set of Arf numerical semigroups with Frobenius number f
## as explained in the preprint
## Rosales et al., Arf numerical semigroups with given genus and Frobenius number
## This version is due to Giuseppe Zito
#############################################################################
InstallGlobalFunction(ArfNumericalSemigroupsWithFrobeniusNumber, function(f)
local n, T, Cond, i,j,k, inarf, filt, al, s;
# tests whether x is in the Arf semigroup with multiplicity
# sequence j
inarf:=function(x,j)
local l;
if x>Sum(j) then
return true;
fi;
if x=0 then
return true;
fi;
if x<j[1] then
return false;
fi;
l:=List([1..Length(j)], i-> Sum(j{[1..i]}));
return x in l;
end;
if(not(IsInt(f))) then
Error("The argument must be an integer");
fi;
n:=f+1;
if (n<0) or (n=1) then
return [];
fi;
if n=0 then
s:=NumericalSemigroup(1);
Setter(IsArfNumericalSemigroup)(s,true);
return [s];
fi;
Cond:=List([[n]]);
T:=[];
for i in [2..n-2] do
T[i]:=[[i]];
od;
for i in [2..n-2] do
for j in T[i] do
if inarf(n-i,j) then
Add(Cond, Concatenation([n-i],j));
fi;
filt:= Filtered([j[1]..Int((n-i)/2)], x->inarf(x,j));
for k in filt do
Add(T[i+k],Concatenation([k],j));
od;
od;
od;
al := List(Cond, j-> NumericalSemigroupBySmallElementsNC(Concatenation([0],List([1..Length(j)], i-> Sum(j{[1..i]})))));
for s in al do
Setter(IsArfNumericalSemigroup)(s,true);
od;
return al;
end);
#####################################################################
##
#F ArfNumericalSemigroupsWithGenus(g)
##
## Returns the set of Arf numerical semigroups with genus g,
## This version is due to Giuseppe Zito
#############################################################################
InstallGlobalFunction(ArfNumericalSemigroupsWithGenus, function(g)
local n, T, Gen, i,j,k, inarf, filt, al, s;
# tests whether x is in the Arf semigroup with multiplicity
# sequence j
inarf:=function(x,j)
local l;
if x>Sum(j) then
return true;
fi;
if x=0 then
return true;
fi;
if x<j[1] then
return false;
fi;
l:=List([1..Length(j)], i-> Sum(j{[1..i]}));
return x in l;
end;
n:=g;
if(not(IsInt(g))) then
Error("The argument must be an integer");
fi;
if (g<0) then
return [];
fi;
if n=0 then
s:=NumericalSemigroup(1);
Setter(IsArfNumericalSemigroup)(s,true);
return [s];
fi;
Gen:=List([[n+1]]);
T:=[];
for i in [1..n-1] do
T[i]:=[[i+1]];
od;
for i in [1..n-1] do
for j in T[i] do
if inarf(n-i+1,j) then
Add(Gen, Concatenation([n-i+1],j));
fi;
filt:= Filtered([j[1]..Int((n-i+2)/2)], x->inarf(x,j));
for k in filt do
Add(T[i+k-1],Concatenation([k],j));
od;
od;
od;
al := List(Gen, j-> NumericalSemigroupBySmallElementsNC(Concatenation([0],List([1..Length(j)], i-> Sum(j{[1..i]})))));
for s in al do
Setter(IsArfNumericalSemigroup)(s,true);
od;
return al;
end);
#####################################################################
##
#F ArfNumericalSemigroupsWithGenusUpTo(g)
##
## Returns the set of Arf numerical semigroups with genus less than
## or equal to g, as explained in
## -Rosales et al., Arf numerical semigroups with given genus and
## Frobenius number
## New version by Giuseppe Zito (U Catania)
#############################################################################
InstallGlobalFunction(ArfNumericalSemigroupsWithGenusUpTo,function(g)
local n, T, i,j,k, inarf, filt, al, s;
# tests whether x is in the Arf semigroup with multiplicity
# sequence j
inarf:=function(x,j)
local l;
if x>Sum(j) then
return true;
fi;
if x=0 then
return true;
fi;
if x<j[1] then
return false;
fi;
l:=List([1..Length(j)], i-> Sum(j{[1..i]}));
return x in l;
end;
n:=g;
if(not(IsInt(g))) then
Error("The argument must be an integer");
fi;
if (g<0) then
return [];
fi;
if n=0 then
s:=NumericalSemigroup(1);
Setter(IsArfNumericalSemigroup)(s,true);
return [s];
fi;
T:=[];
for i in [1..n] do
T[i]:=[[i+1]];
od;
T[n+1]:=[[1]];
for i in [1..n-1] do
for j in T[i] do
filt:= Filtered([j[1]..n-i+1], x->inarf(x,j));
for k in filt do
Add(T[i+k-1],Concatenation([k],j));
od;
od;
od;
al :=List(Union(T),j-> NumericalSemigroupBySmallElementsNC(Concatenation([0],List([1..Length(j)], i-> Sum(j{[1..i]})))));
for s in al do
Setter(IsArfNumericalSemigroup)(s,true);
od;
return al;
end);
#####################################################################
##
#F ArfNumericalSemigroupsWithFrobeniusNumberUpTo(f)
##
## Returns the set of Arf numerical semigroups with Frobenius number
## less than or equal to f, as explained in
## Rosales et al., Arf numerical semigroups with given genus and Frobenius number
## New version by Giuseppe Zito (U Catania)
#############################################################################
InstallGlobalFunction(ArfNumericalSemigroupsWithFrobeniusNumberUpTo,function(f)
local n, T, i,j,k, inarf, filt, al, s;
# tests whether x is in the Arf semigroup with multiplicity
# sequence j
inarf:=function(x,j)
local l;
if x>Sum(j) then
return true;
fi;
if x=0 then
return true;
fi;
if x<j[1] then
return false;
fi;
l:=List([1..Length(j)], i-> Sum(j{[1..i]}));
return x in l;
end;
if(not(IsInt(f))) then
Error("The argument must be an integer");
fi;
n:=f+1;
if (n<0) or (n=1) then
return [];
fi;
if n=0 then
s:=NumericalSemigroup(1);
Setter(IsArfNumericalSemigroup)(s,true);
return [s];
fi;
T:=[];
for i in [1..n] do
T[i]:=[[i]];
od;
for i in [2..n-2] do
for j in T[i] do
filt:= Filtered([j[1]..n-i], x->inarf(x,j));
for k in filt do
Add(T[i+k],Concatenation([k],j));
od;
od;
od;
al:=List(Union(T),j-> NumericalSemigroupBySmallElementsNC(Concatenation([0],List([1..Length(j)], i-> Sum(j{[1..i]})))));
for s in al do
Setter(IsArfNumericalSemigroup)(s,true);
od;
return al;
end);
#####################################################################
##
#F ArfNumericalSemigroupsWithGenusAndFrobeniusNumber(g,f)
##
## Returns the set of Arf numerical semigroups with genus g and
## Frobenius number f, as explained in
## Rosales et al., Arf numerical semigroups with given genus and Frobenius number
#############################################################################
InstallGlobalFunction(ArfNumericalSemigroupsWithGenusAndFrobeniusNumber,function(g,f)
local par2sem, testArfSeq, arfsequences, n, al, s;
#transforms a partition list of an element to the set of sums
# which will correspond with the set of small elements of the semigroup
par2sem:=function(l)
local rl, n,sm, i;
n:=Length(l);
rl:=Reversed(l);
sm:=[0];
for i in [1..n] do;
Add(sm,Sum(rl{[1..i]}));
od;
return sm;
end;
# computes all Arf sequences with sumset equal f+1
arfsequences:=function(n)
local l, k, lk, lkm1,bound,cand,s;
l:=[List([2..Int(f+1)], x-> [x])];
for k in [2..n] do
lk:=[];
lkm1:=l[Length(l)];
for s in lkm1 do
bound:=Int((f+1-Sum(s))/(n-(k-1)));
cand:=Intersection(Union(Difference(par2sem(s),[0]), [Sum(s)..bound]),[s[Length(s)]..bound]);
lk:=Concatenation(lk,List(cand,x->Concatenation(s,[x])));
od;
if lk<>[] then
l:=Concatenation(l,[lk]);
fi;
od;
l:=Filtered(l[n], x->Sum(x)=f+1);
return l;
end;
if not(IsInt(g)) or not(IsInt(f)) then
Error("The arguments must be an integers");
fi;
if g<0 then
return [];
fi;
if g=0 and f=-1 then
s:=NumericalSemigroup(1);
Setter(IsArfNumericalSemigroup)(s,true);
return [s];
fi;
if not(g<=f and f<=2*g-1) then
return [];
fi;
n:=f+1-g;
al:=List(List(arfsequences(n), par2sem),NumericalSemigroupBySmallElementsNC);
for s in al do
Setter(IsArfNumericalSemigroup)(s,true);
od;
return al;
end);
#####################################################################
##
## ArfSpecialGaps(s)
##
## returns the set of gaps g of s such that s cup {g} is again Arf
##
#####################################################################
InstallMethod(ArfSpecialGaps,
"Returns Arf special gaps",
[IsNumericalSemigroup],
function(s)
local ag, sg, g, se, rse, e1, e2;
if not(IsArf(s)) then
Error("The argument must be an Arf numerical semigroup");
fi;
ag:=[];
sg:=SpecialGaps(s);
se:=SmallElements(s);
rse:=Reversed(se);
for g in sg do
e1:=First(rse, e->g-e>0);
e2:=First(se, e->g-e<0);
if (2*g-e1 in s) and (2*e2-g in s) then
Add(ag,g);
fi;
od;
return ag;
end);
#####################################################################
##
## ArfOverSemigroups(s)
##
## returns the set of Arf oversemigroups of s
##
#####################################################################
InstallMethod(ArfOverSemigroups,
"Returns the set of Arf oversemigroups of the given numerical semigroup",
[IsNumericalSemigroup],
function(s)
local t, sg, A, O, g, a;
if(not(IsArf(s))) then
Error("The argument must be an Arf numerical semigroup");
fi;
if(s=NumericalSemigroup(1)) then
return [s];
fi;
t:=s;
sg:=ArfSpecialGaps(t); #which must be different from [-1]
A:=[NumericalSemigroup(1),t];
O:=[];
for g in sg do #List(sg,g->AddSpecialGapOfNumericalSemigroup(g,t));
a:=AddSpecialGapOfNumericalSemigroup(g,t);
Setter(IsArf)(a,true);
AddSet(O,a);
od;
while(not(O=[])) do
t:=O[1];
O:=O{[2..Length(O)]};
if(not(t in A)) then
A:=Union(A,[t]);
sg:=ArfSpecialGaps(t);
for g in sg do #O:=Union(O,List(sg,g->AddSpecialGapOfNumericalSemigroup(g,t)));
a:=AddSpecialGapOfNumericalSemigroup(g,t);
Setter(IsArf)(a,true);
AddSet(O,a);
od;
fi;
od;
return A;
end);
#####################################################################
##
## IsArfIrreducible(s)
##
## detects it s can be written as the intersection of two or more
## Arf semigroups containing it
##
#####################################################################
InstallMethod(IsArfIrreducible,
"Tests wether the semigroup is Arf irreducible",
[IsNumericalSemigroup],
function(s)
if not(IsArf(s)) then
Error("The argument must be an Arf numerical semigroup");
fi;
return Length(ArfSpecialGaps(s))<=1;
end);
InstallTrueMethod(IsArfIrreducible, IsArf and IsArfIrreducible);
#####################################################################
##
## DecomposeIntoArfIrreducibles(s)
##
## retuns a set of Arf irreducible numerical semigroups whose
## intersection is s; this representation is minimal in the sense
## that no semigroup can be removed
##
#####################################################################
InstallMethod(DecomposeIntoArfIrreducibles,
"retuns the Arf irreducible numerical semigroups whose intersection is the arguement",
[IsNumericalSemigroup],
function(s)
local sg, caux, I, C, B, pair, i, I2, j, l, dec, si;
#sg contains the special gaps of s
#B auxiliar ser used to construct C and I
#I will include Arf irreducibles containing s
#C non irreducibles
#caux(t) is to compute those elements in gs that are not in t
#II auxiliar set of Arf irreducibles
if(not(IsNumericalSemigroup(s))) then
Error("The argument must be a numerical semigroup.\n");
fi;
if(not(IsArf(s))) then
Error("The argument must be an Arf numerical semigroup.\n");
fi;
if(s=NumericalSemigroup(1)) then
Setter(IsIrreducibleNumericalSemigroup)(s,true);
return [s];
fi;
sg:=ArfSpecialGaps(s);
if (Length(sg)=1) then
#Setter(IsIrreducibleNumericalSemigroup)(s,true);
return [s];
fi;
caux:=function(t)
return Filtered(sg,g->not(BelongsToNumericalSemigroup(g,t)));
end;
I:=[];
C:=[s];
B:=[];
while(not(C=[])) do
B:=Union(List(C,sp->List(ArfSpecialGaps(sp),g->AddSpecialGapOfNumericalSemigroup(g,sp))));
B:=Filtered(B,b->not(caux(b)=[]));
B:=Filtered(B,b->Filtered(I,i->IsSubsemigroupOfNumericalSemigroup(i,b))=[]);
C:=Filtered(B,b->not(Length(ArfSpecialGaps(b))=1));
I:=Union(I,Difference(B,C));
od;
I:=List(I,i->[i,caux(i)]);
while(true) do
pair := fail;
for i in I do
I2 := [];
for j in I do
if not j = i then
Add(I2, j);
fi;
od;
l := [];
for j in I2 do
Add(l, j[2]);
od;
if Union(l) = sg then
pair := i;
break;
fi;
od;
if(pair=fail) then
dec:=List(I, x -> x[1]);
for si in dec do
Setter(IsArfIrreducible)(si,true);
od;
return dec;
fi;
I2 := [];
for j in I do
if not j = pair then
Add(I2, j);
fi;
od;
I := I2;
Unbind(I2);
od;
dec:=List(I, x -> x[1]);
for si in dec do
Setter(IsArfIrreducible)(si,true);
od;
return dec;
end);
#####################################################################
## MED
## See [RGGB03]
#####################################################################
##
#A IsMEDNumericalSemigroup(s)
##
## The argument s is a numerical semigroup
## returns true if s is a MED-semigroup and false otherwise
##
#####################################################################
InstallMethod(IsMEDNumericalSemigroup,
"Tests if a numerical semigroup is a MED-semigroup",
[IsNumericalSemigroup],
function(s)
local e, m;
m := MultiplicityOfNumericalSemigroup(s);
e := Length(MinimalGeneratingSystemOfNumericalSemigroup(s));
return e = m;
end);
#####################################################################
##
#F MEDNumericalSemigroupClosure(arg)
##
## The argument may be a numerical semigroup or a list of relatively prime
## positive integers
## The output is the MED-closure of arg (the smallest MED-semigroup
## containing arg)
##
#####################################################################
InstallGlobalFunction(MEDNumericalSemigroupClosure, function(arg)
local set, min, A, small, s;
if Length(arg) = 1 and IsNumericalSemigroup(arg[1]) then
if HasMinimalGeneratingSystemOfNumericalSemigroup(arg[1]) then
set := MinimalGeneratingSystemOfNumericalSemigroup(arg[1]);
else
set := GeneratorsOfNumericalSemigroup(arg[1]);
fi;
elif Length(arg) = 1 then
if Gcd(arg[1]) <> 1 then
Error("The greatest common divisor is not 1");
fi;
set := arg[1];
else
if Gcd(arg) <> 1 then
Error("The greatest common divisor is not 1");
fi;
set := arg;
fi;
set := Set(set);
min := Minimum(set);
if min <= 0 then
Error("The elements of the list must be positive integers");
fi;
A := set - min;
A[1] := min;
small := Union([0], min +
SmallElementsOfNumericalSemigroup(NumericalSemigroup(A)));
s:= NumericalSemigroupBySmallElements(small);
Setter(IsMEDNumericalSemigroup)(s,true);
return s;
end);
InstallMethod(MEDClosure,
"Computes the MED closure of a numerical semigroup",
[IsNumericalSemigroup],
MEDNumericalSemigroupClosure
);
#####################################################################
##
#A MinimalMEDGeneratingSystemOfMEDNumericalSemigroup(s)
##
## The argument s is a MED numerical semigroup
## returns the minimal MED-generating system of s.
##
#############################################################################
InstallMethod(MinimalMEDGeneratingSystemOfMEDNumericalSemigroup,
"Returns the minimal MED-generating system of a MED numerical semigroup",
[IsNumericalSemigroup],
function(s)
local gen, len, ngen;
if not IsMEDNumericalSemigroup(s) then
Error("s must be a MED numerical semigroup");
fi;
gen := MinimalGeneratingSystemOfNumericalSemigroup(s);
len := Length(gen);
if len = 2 then
return gen;
fi;
while len >= 2 do
ngen := Difference(gen, [gen[len]]);
if Gcd(ngen) = 1 and s = MEDNumericalSemigroupClosure(ngen) then
gen := ngen;
len := len - 1;
else
len := len -1;
fi;
od;
return gen;
end);
#####################################################################
## Saturated
## See [book]
#####################################################################
##
#F SaturatedfNumericalSemigroupClosure(arg)
##
## The argument may be a numerical semigroup or a list of relatively prime
## positive integers
## The output is the saturated-closure of arg (the smallest saturated-semigroup
## containing arg)
##
#####################################################################
InstallGlobalFunction(SaturatedNumericalSemigroupClosure, function(arg)
local set, gen, min, ne, edim, dis, small, i, kjs, s;
if Length(arg) = 1 and IsNumericalSemigroup(arg[1]) then
if HasMinimalGeneratingSystemOfNumericalSemigroup(arg[1]) then
set := MinimalGeneratingSystemOfNumericalSemigroup(arg[1]);
else
set := GeneratorsOfNumericalSemigroup(arg[1]);
fi;
elif Length(arg) = 1 then
if Gcd(arg[1]) <> 1 then
Error("The greatest common divisor is not 1");
fi;
set := arg[1];
else
if Gcd(arg) <> 1 then
Error("The greatest common divisor is not 1");
fi;
set := arg;
fi;
gen := Set(set);
min := gen[1];
ne := Maximum(gen);
if not IsPosInt(min) then
Error("The elements of the list must be positive integers");
fi;
edim := Length(gen); #embedding dimension
dis := List([1..edim], i -> Gcd(gen{[1..i]}));
small := Set([0]);
for i in [1..edim-1] do
kjs := 0;
if (dis[i] = 1) then
return NumericalSemigroupBySmallElements(Union(small,[gen[i]]));
fi;
while(gen[i] + kjs*dis[i] < gen[i+1]) do
AddSet(small,gen[i]+kjs*dis[i]);
kjs := kjs+1;
od;
od;
s:=NumericalSemigroupBySmallElements(Union(small,[ne]));
Setter(IsSaturatedNumericalSemigroup)(s,true);
return s;
end);
InstallMethod(SaturatedClosure,
"Computes the Saturated closure of a numerical semigroup",
[IsNumericalSemigroup],
SaturatedNumericalSemigroupClosure
);
#####################################################################
##
#P IsSaturatedNumericalSemigroup(s)
##
## The argument s is a numerical semigroup
## returns true if s is a saturated-semigroup and false otherwise
##
#####################################################################
InstallMethod(IsSaturated,
"Tests if a Numerical Semigroup is a saturated semigroup",
[IsNumericalSemigroup],
function(s)
return (s = SaturatedNumericalSemigroupClosure(s));
end);
# InstallMethod(IsSaturated,
# "Tests if a Numerical Semigroup is a saturated semigroup",
# [IsNumericalSemigroup],IsSaturatedNumericalSemigroup);
#solution by Sebastian Gutsche to
InstallTrueMethod(IsArfNumericalSemigroup, IsSaturatedNumericalSemigroup);
#####################################################################
##
#F SaturatedNumericalSemigroupsWithFrobeniusNumber(f)
##
## The argument f is an integer
## returns the the set of saturated numerical semigroups with Frobenius number f
## as explained in the preprint
## Rosales et al., Arf numerical semigroups with given genus and Frobenius number
#############################################################################
InstallGlobalFunction(SaturatedNumericalSemigroupsWithFrobeniusNumber,function(f)
local alg23, alg24, satpart, listsatseq, L, C, Ll, l, t, satsystem, i, ls, s;
if(not(IsInt(f))) then
Error("The argument must be an integer.\n");
fi;
if f=0 or f<-1 then
return [];
fi;
if f=-1 then
s:=NumericalSemigroup(1);
Setter(IsSaturatedNumericalSemigroup)(s,true);
return [s];
fi;
#returns the set nonnegative integer of solutions x
# with l.x=c; l is a (saturated) sequence
# l[i+1]|l[i], l[i+1]<>l[i], l[Length(l)]=1
satpart:=function(l,c)
local sols, len, i, j, sol, next, cand;
len:=Length(l);
sol:=[];
for i in [1..len-1] do Add(sol, 0); od;
sol[len]:=c;
sols:=[sol];
while true do
j:=First(Reversed([1..len-1]), i-> sol{[i+1..len]}*l{[i+1..len]}>=l[i]);
if j=fail then
return sols;
fi;
next:=[];
for i in [1..j-1] do next[i]:=sol[i]; od;
next[j]:=sol[j]+1;
for i in [j+1..len-1] do next[i]:=0; od;
next[len]:=sol{[j+1..len]}*l{[j+1..len]}-l[j];
sol:=next;#sol:=ShallowCopy(next);
Add(sols, sol);
od;
end;
#returns saturated semigroups associated to a saturaded sequence
# with Frobenius number f
listsatseq:=function(d, f)
local c, l, ok, sum, len, ones, i;
l:=[];
ok:=false;
sum:=Sum(d);
len:=Length(d);
if (f+1>=sum) and (Gcd(f+1,d[len-1])=1) and (((f+1) mod d[len-1])<>1) then
ok:=true;
c:=f+1-sum;
fi;
if (f+2>=sum) and (((f+2) mod d[len-1])=1) then
ok:=true;
c:=f+2-sum;
fi;
if not(ok) then
return [];
fi;
ones:=[];
for i in [1..len] do ones[i]:=1; od;
l:=satpart(d,c);
l:=l+ones;
l:=Filtered(l, t-> ForAll([1..len-1], i-> Gcd(d[i]/d[i+1],t[i+1])=1));
return l;
end;
#implements Algorithm 23
alg23:=function(f)
local tot, A, AA, cand, d, x, dd;
cand:=Filtered([2..f], x-> Gcd(f+1,x)=1 and f mod x<> 0);
A:=List(cand, x-> [x,1]);
tot:=A;
while (A<>[]) do
AA:=[];
for d in A do
for x in [2..Int((f+1-Sum(d))/d[1])] do
dd:=ShallowCopy(d);
dd[1]:=x*d[1];
dd{[2..Length(d)+1]}:=d;
Add(AA, dd);
od;
od;
A:=AA;
tot:=Union(tot,A);
od;
return tot;
end;
#implements Algorithm 24
alg24:=function(f)
local tot, A, AA, cand, d, x, dd;
cand:=Difference(DivisorsInt(f+1),[1]);
A:=List(cand, x-> [x,1]);
tot:=A;
while (A<>[]) do
AA:=[];
for d in A do
for x in [2..Int((f+2-Sum(d))/d[1])] do
dd:=ShallowCopy(d);
dd[1]:=x*d[1];
dd{[2..Length(d)+1]}:=d;
Add(AA, dd);
od;
od;
A:=AA;
tot:=Union(tot,A);
od;
return tot;
end;
#main
L:=Union(alg23(f),alg24(f));
C:=[];
for l in L do
Ll:=listsatseq(l,f);
for t in Ll do
satsystem:=[];
satsystem[1]:=l[1];
for i in [2..Length(l)] do
satsystem[i]:=l{[1..i]}*t{[1..i]};
od;
Add(C,satsystem);
od;
od;
ls:=Set(C, SaturatedNumericalSemigroupClosure);
for s in ls do
Setter(IsSaturatedNumericalSemigroup)(s,true);
od;
return ls;
end);
[ Dauer der Verarbeitung: 0.40 Sekunden
(vorverarbeitet)
]
|
