#OK to post homework
#Joseph Koutsoutis, 03-24-2024, Assignment 17

read `hw16JosephKoutsoutis.txt`:
read `C17.txt`:

#1


PolToList := proc(P,x) local d,i,L:
 d := degree(P):
 L := []:
 for i from 1 to d do:
  if coeff(P, x, i) <> 0 then:
   L := [op(L), i]:
  fi:
 od: 

 return(L):
end:


MaxPer := proc(d,x) local pols,pol,p,L,INI:
 pols := PolsE(x,d):
 p := 2^d - 1:
 L := {}:
 INI := [1,0$(d-1)]:
 for pol in pols do:
  if FindPer(SR(INI, PolToList(pol,x), 2*p)) = p then:
   L := L union {pol}:
  fi:
 od:
 L:
end:

# running {seq(evalb(MaxPer(d,x)=WisW(d,x)[4]), d=3..10)} outputted {true} as expected


#2

qPolToList := proc(P,x) local d,i,L:
 d := degree(P):
 L := []:
 for i from 1 to d do:
  if coeff(P, x, i) <> 0 then:
   L := [op(L), [coeff(P, x, i), i]]:
  fi:
 od: 

 return(L):
end:

qPols := proc(q,x,d) local S,s,i:
 option remember:
 if d=0 then
  return({seq(i, i=1..q-1)}):
 fi:
 S:=qPols(q,x,d-1):
 S union {seq(seq(s+i*x^d,s in S), i=1..q-1)}:
end:


qPolsE := proc(q,x,d) local S,s,i:
 S:=qPols(q,x,d-1):
 {seq(seq(s+i*x^d,s in S), i=1..q-1)}:
end:

qIsIr := proc(q,P)
 option remember:
 evalb(Factor(P) mod q=P mod q):
end:


qIsPr := proc(q,P,x) local d,m,i:
 option remember:
 d:=degree(P,x):
 m:=q^d-1:
 for i from 1 to m-1 do
  if rem(x^i,P,x) mod q=1 then
   return(false):
  fi:
 od:
 if rem(x^m,P,x) mod q<>1 then
  print(`we messed up`):
  return(FAIL):
 fi:
 return(true): 
end:


qWisW := proc(q,d,x) local S,s, Si, Sp, Sip, Sne:
 #Si:=set of pol. of degree d (mod 2) that are irreducible but NOT primitive
 #Sp:=set of pol. of degree d (mod 2) that are NOT irreducible but  primitive
 #Sip:=set of pol. of degree d (mod 2) that are BOTH irreducible and  primitive
 #Sne= neither
 S:=qPolsE(q,x,d):
 Si:={}: Sp:={}: Sip:={}: Sne:={}:

 for s in S do
  if qIsIr(q,s) and not qIsPr(q,s,x) then
   Si:=Si union {s}:
  elif  not qIsIr(q,s) and  qIsPr(q,s,x) then
   Sp:=Sp union {s}:
  elif   qIsIr(q,s) and  qIsPr(q,s,x) then
   Sip:=Sip union {s}:
  else
   Sne:=Sne union {s}:
  fi:
 od:
 [Sne,Si,Sp,Sip]:
end:


qMaxPer := proc(q,d,x) local pols,pol,p,L,INI:
 pols := qPolsE(q,x,d):
 p := (q^d - 1):
 L := {}:
 INI := [1,0$(d-1)]:
 for pol in pols do:
  if FindPer(qSR(q,INI, qPolToList(pol,x), 2*p)) = p then:
   L := L union {pol}:
  fi:
 od:
 L:
end:


# The output I got when running {seq(evalb(qMaxPer(3,d,x)=qWisW(3,d,x)[4]), d=3..5)} was {false}.


#3 done