|
#############################################################################
##
#W number.gi GAP4 package `Utils' Stefan Kohl
##
#Y Copyright (C) 2015-2025, The GAP Group
#############################################################################
## this function has been transferred from RCWA
##
#F AllSmoothIntegers( <maxp>, <maxn> )
#F AllSmoothIntegers( <primes>, <maxn> )
##
BindGlobal( "AllSmoothIntegers",
function ( maxp, maxn )
local extend, nums, primes, p;
extend := function ( n, mini )
local i;
if n > maxn then return; fi;
Add(nums,n);
for i in [mini..Length(primes)] do
extend(primes[i]*n,i);
od;
end;
if IsInt(maxp)
then primes := Filtered([2..maxp],IsPrimeInt);
elif IsList(maxp) and ForAll(maxp,p->IsInt(p) and IsPrimeInt(p))
then primes := maxp;
else return fail; fi;
if not IsPosInt(maxn) then return fail; fi;
nums := [];
extend(1,1);
return Set(nums);
end );
#############################################################################
## this function has been transferred from RCWA
##
#F NextProbablyPrimeInt( <n> ) . . next integer passing `IsProbablyPrimeInt'
##
BindGlobal( "NextProbablyPrimeInt",
function ( n )
if -3 = n then n := -2;
elif -3 < n and n < 2 then n := 2;
elif n mod 2 = 0 then n := n+1;
else n := n+2;
fi;
while not IsProbablyPrimeInt(n) do
if n mod 6 = 1 then n := n+4;
else n := n+2;
fi;
od;
return n;
end );
#############################################################################
## this function has been transferred from RCWA
##
#F RestrictedPartitionsWithoutRepetitions( <n>, <S> )
##
## Given a positive integer n and a set of positive integers S, this func-
## tion returns a list of all partitions of n into distinct elements of S.
## The only difference to `RestrictedPartitions' is that no repetitions are
## allowed.
##
BindGlobal( "RestrictedPartitionsWithoutRepetitions",
function ( n, S )
local look, comps;
look := function ( comp, remaining_n, remaining_S )
local newcomp, newremaining_n, newremaining_S, part, l;
l := Reversed(remaining_S);
for part in l do
newcomp := Concatenation(comp,[part]);
newremaining_n := remaining_n - part;
if newremaining_n = 0 then Add(comps,newcomp);
else
newremaining_S := Set(Filtered(remaining_S,
s->s<part and s<=newremaining_n));
if newremaining_S <> [] then
look(newcomp,newremaining_n,newremaining_S);
fi;
fi;
od;
end;
comps := [];
look([],n,S);
return comps;
end );
#############################################################################
## this function has been transferred from RCWA
##
#F PrimeNumbersIterator( )
#F PrimeNumbersIterator( chunksize )
##
BindGlobal( "PrimeNumbersIterator",
function ( arg )
local next, copy, chunksize, maxdiv, nrdivs, offset;
if Length(arg) >= 1 and IsPosInt(arg[1])
then chunksize := Maximum(arg[1],100); # must be bigger than largest
else chunksize := 10000000; fi; # prime gap in range looped over
maxdiv := RootInt(chunksize);
offset := List(Filtered([2..maxdiv],IsPrimeInt),p->[p,0]);
nrdivs := Length(offset);
return IteratorByFunctions( rec(
NextIterator := function ( iter )
local sieve, range, p, q, pos, endpos, maxdiv_old, maxdiv, i, j;
if iter!.index = 0 then
sieve := ListWithIdenticalEntries(iter!.chunksize,0);
if iter!.n = 0 then sieve[1] := 1; fi;
for i in [1..iter!.nrdivs] do
p := iter!.offset[i][1];
if p > iter!.n then pos := 2 * p;
else pos := iter!.offset[i][2];
fi;
if pos = 0 then pos := p; fi;
endpos := pos + Int((iter!.chunksize-pos)/p) * p;
if pos <= iter!.chunksize then
range := [pos,pos+p..endpos];
if IsRangeRep(range) then
ADD_TO_LIST_ENTRIES_PLIST_RANGE(sieve,range,1);
else
for j in range do sieve[j] := sieve[j] + 1; od;
fi;
fi;
if endpos <= iter!.chunksize then
iter!.offset[i][2] := endpos + p - iter!.chunksize;
else
iter!.offset[i][2] := iter!.offset[i][2] - iter!.chunksize;
fi;
od;
iter!.primepos := Positions(sieve,0);
fi;
iter!.index := iter!.index + 1;
p := iter!.n + iter!.primepos[iter!.index];
iter!.p := p;
iter!.pi := iter!.pi + 1;
if iter!.index = Length(iter!.primepos) then
iter!.index := 0;
iter!.n := iter!.n + iter!.chunksize;
maxdiv_old := iter!.maxdiv;
iter!.maxdiv := RootInt(iter!.n + iter!.chunksize);
for q in Filtered([maxdiv_old+1..iter!.maxdiv],IsPrimeInt) do
Add(iter!.offset,[q,(q-iter!.n) mod q]);
od;
iter!.nrdivs := Length(iter!.offset);
fi;
return p;
end,
ShallowCopy := function ( iter )
return rec( chunksize := iter!.chunksize,
n := iter!.n,
p := iter!.p,
pi := iter!.pi,
index := iter!.index,
primepos := ShallowCopy(iter!.primepos),
nrdivs := iter!.nrdivs,
maxdiv := iter!.maxdiv,
offset := StructuralCopy(iter!.offset) );
end,
IsDoneIterator := ReturnFalse,
chunksize := chunksize,
n := 0,
p := 0,
pi := 0,
index := 0,
primepos := [],
nrdivs := nrdivs,
maxdiv := maxdiv,
offset := offset ) );
end );
#############################################################################
## this function has been transferred from RCWA
##
#M AllProducts( <D>, <k> ) . . all products of <k>-tuples of elements of <D>
#M AllProducts( <l>, <k> ) . . . . . . . . . . . . . . . . . . . . for lists
##
InstallMethod( AllProducts,
"for lists (RCWA)", ReturnTrue, [ IsList, IsPosInt ], 0,
function(l,k) return List(Tuples(l,k),Product); end );
#############################################################################
##
#E number.gi . . . . . . . . . . . . . . . . . . . . . . . . . . . ends here
[ Dauer der Verarbeitung: 0.5 Sekunden
(vorverarbeitet)
]
|
