# OK to post homework
# Alex Varjabedian, 21-Mar-2024, Homework 16

Help := proc() print(`qSR(q, INI, L, n)`) end:

IsPer:=proc(L,t) local i:
if {seq(L[i]-L[i+t],i=1..nops(L)-t)}={0} then
  true:
else
 false:
fi:
end:

FindPer:=proc(L) local t:
for t from 1 to trunc(nops(L)/2) while not IsPer(L,t) do od:
if t=trunc(nops(L)/2)+1 then
RETURN(FAIL):
else
 RETURN(t):
fi:
end:


###########################
# ----------------------- #
# PART 2 - qSR(q,INI,L,n) #
# ----------------------- #
###########################

print(`PART 2`);

qSR:=proc(q,INI,L,n) local r,i,M,ng:
r:=nops(L):
if nops(INI)<>L[-1][2] then
 RETURN(FAIL):
fi:
if not (sort(INI)[-1] < q and sort(INI)[1] >= 0) then
 RETURN(FAIL):
fi:
if not (type(L, list) and {seq(type(L[i], list), i=1..nops(L))} = {true} and {seq(type(L[i][1], posint), i=1..nops(L))} = {true} and {seq(type(L[i][2], posint), i=1..nops(L))} = {true} and sort([seq(L[i][1], i=1..nops(L))])[-1] < q and sort([seq(L[i][1], i=1..nops(L))])[1] >= 0 and sort([seq(L[i][2], i=1..nops(L))]) = [seq(L[i][2], i=1..nops(L))]) then
   RETURN(FAIL):
fi:
if not type(n,posint) then
     RETURN(FAIL):
fi:

M:=INI:

while(nops(M))<n do
 ng:=add(L[i][1]*M[-L[i][2]],i=1..r) mod q:
 M:=[op(M),ng]:
od:
M:

end:

# Example
print(`Example`);
printf("%a\n", qSR(3,[1,2,1],[[1,2],[2,3]],10000));

####################
# ---------------- #
# PART 3 - Periods #
# ---------------- #
####################

print(`PART 3`);

printf("The periods of qSR(3,[1,2,1],[[1,2],[2,3]],10000), qSR(5,[1,2,4,1,2],[[1,2],[2,5]],10000), qSR(11,[3,1,2,4,3],[[1,2],[2,5]],10000), and qSR(5,[1,0,0,0,0,0],[[3,4],[2,5],[3,6]],10000) are:\n%a, %a, %a, and %a\n", FindPer(qSR(3,[1,2,1],[[1,2],[2,3]],10000)), FindPer(qSR(5,[1,2,4,1,2],[[1,2],[2,5]],10000)), FindPer(qSR(11,[3,1,2,4,3],[[1,2],[2,5]],10000)), FindPer(qSR(5,[1,0,0,0,0,0],[[3,4],[2,5],[3,6]],10000)));