#Nuray Kutlu March 24
#OK TO POST
#March 21, 2024, C17.txt
MaxPer:=proc(d,x) local S,s,i,L,RES:
RES:={}:
S:=PolsE(x,d):
for s in S do
 L:=PolToList(2,s,x,d):
 if FindPer(SR([1,0$(d-1)],L,10*(2^d -1)))= (2^d-1) then
  RES:=RES union s
 fi:
od:
end:

#seq(evalb(MaxPer(d, x) = WisW(d, x)[4]), d = 3 .. 10): 
#false, false, false, false, false, false, false, false


PolToList:=proc(q,P,x,d) local i: [seq(coeff(P,x, i) mod q, i=0..d)]:end:


qPols:=proc(q,x,d) local S,s,i:
option remember:
if d=0 then
 RETURN({seq(i, i=0..q-1)}):
fi:
i:=0:
S:=qPols(q,x,d-1):
S union {seq(seq(s+i*x^d,s in S),i=0..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:

qIsPr:=proc(q,P,x) local d,m,i:
option remember:
d:=degree(P,x):
m:=2^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
RETURN(FAIL):
fi:
true:
end:

qWisW:=proc(q,d,x) local S,s, Si, Sp, Sip, Sne:
S:=qPolsE(q,x,d):
Si:={}: Sp:={}: Sip:={}: Sne:={}:
for s in S do
 if IsIr(s) and not qIsPr(s,x) then
   Si:=Si union {s}:
  elif  not IsIr(s) and  qIsPr(s,x) then
    Sp:=Sp union {s}:
  elif   IsIr(s) and  qIsPr(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 S,s,i,L,RES:
RES:={}:
S:=PolsE(x,d):
for s in S do
 L:=PolToList(q,s,x,d):
 if FindPer(SR([1,0$(d-1)],L,10*(2^d -1)))= (2^d-1) then
  RES:=RES union s
 fi:
od:
end:

#old code
#C16.txt, March 18, 2024
Help16:=proc(): print(`SR(INI,L,n), IsPer1(L,t), FindPer(L) `):end:

#SR(INI,L,n): inputs a 0-1 list of length L[nops(L)]
# a list of increasing positive integers L, and outputs
#the sequence of 0-1 generated by them of length n
#outputs the list of length n generated by the recurrence
#x[t]=x[t-L[1]]+...+x[t-L[nops(L)]
SR:=proc(INI,L,n) local r,i,M,ng:
r:=nops(L):
if nops(INI)<>L[-1] then
 RETURN(FAIL):
fi:

if not (convert(INI,set)={0,1} or convert(INI,set)={1}) then
 RETURN(FAIL):
fi:

if not (type(L,list) and {seq(type(L[i],posint),i=1..nops(L))}={true} and sort(L)=L) then
   RETURN(FAIL):
fi:
if not type(n,posint) then
     RETURN(FAIL):
fi:

M:=INI:

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

end:

#IsPer(L,t): Is L periodic of period t?
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:

#end old code

#start new code for C17.txt
#Pols(x,d): The SET of all polynomials of degree <=d in x mod 2 such that the constant term is 1
Pols:=proc(x,d) local S,s:
option remember:
if d=0 then
 RETURN({1}):
fi:
S:=Pols(x,d-1):
S union {seq(s+x^d,s in S)}:
end:

#PolsE(x,d): The set of polynomials of EXACTLY degree d
PolsE:=proc(x,d) local S,s:
S:=Pols(x,d-1):
{seq(s+x^d, s in S)}:
end:

#IsIr(P): Is P irreducible mod 2?
IsIr:=proc(P)
option remember:
evalb(Factor(P) mod 2=P mod 2):
end:

#IsPr(P,x): is the polynomial P in x of degree d, say, primitive?
IsPr:=proc(P,x) local d,m,i:
option remember:
d:=degree(P,x):
m:=2^d-1:
 for i from 1 to m-1 do
   if rem(x^i,P,x) mod 2=1 then
     RETURN(false):
   fi:
od:
if rem(x^m,P,x) mod 2<>1 then
   print(`Something bad happened, Cocks' aritcle is wrong!, or more likely (according to George)`):
   print(`we messed up`):
    RETURN(FAIL):
fi:
true: 
end:

#WisW(d,x): inputs a pos. integer d and outputs the list of sets
#of pol. of degree exactly d such that
#(i) neither (ii) Irred. but not Primitive (iii) Primitive but not irreducible (iv) both
WisW:=proc(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:=PolsE(x,d):
Si:={}: Sp:={}: Sip:={}: Sne:={}:

for s in S do
 if IsIr(s) and not IsPr(s,x) then
   Si:=Si union {s}:
  elif  not IsIr(s) and  IsPr(s,x) then
    Sp:=Sp union {s}:
  elif   IsIr(s) and  IsPr(s,x) then
    Sip:=Sip union {s}:
   else
     Sne:=Sne union {s}:
  fi:
 od:

[Sne,Si,Sp,Sip]:
end: