#Please do not post homework
#Caroline Cote, Feb 22nd, 2026, Assignment 8
Helphw8:= proc(): print(``): end:


read "C3.txt":
read "C4.txt":
read "C5.txt":
read "C6.txt":
read "C7.txt":
read "C8.txt":
read "C9.txt":

with(combinat):

#problem 1

L := [];
for p to 41 do
    if isprime(p) then L := [op(L), (xnP(p - 1, p) + p - 1)*xnP(p - 1, p) mod p]; end if;
end do;
L;
#            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

((xnP(43 - 1, 43) + 43) - 1)*xnP(43 - 1, 43) mod 43;
#                               24

#therefore, xn(43) is not an integer


#problem 2:
#i used Austin's Foata 

perms := permute(7);
seq(evalb(nops(LtoR(FoataA(pi))) = nops(CycDec(pi))), pi in perms);

perms := permute(6);
seq(evalb(nops(LtoR(FoataA(pi))) = nops(CycDec(pi))), pi in perms);


perms := permute(5);
seq(evalb(nops(LtoR(FoataA(pi))) = nops(CycDec(pi))), pi in perms);


perms := permute(4);
seq(evalb(nops(LtoR(FoataA(pi))) = nops(CycDec(pi))), pi in perms);


perms := permute(3);
seq(evalb(nops(LtoR(FoataA(pi))) = nops(CycDec(pi))), pi in perms);


perms := permute(2);
seq(evalb(nops(LtoR(FoataA(pi))) = nops(CycDec(pi))), pi in perms);


perms := permute(1);
seq(evalb(nops(LtoR(FoataA(pi))) = nops(CycDec(pi))), pi in perms);

#too many trues to copy and paste but all 7 produced all trues.


#problem 3
#im convinced

#problem 4

#AntiFoata(pi): inverse of Foata(pi) 
AntiFoata:= proc(pi) local n, lefts, i, cycs, start, b, G:

n:= nops(pi):

lefts:=  LtoR(pi): 

cycs:=[]:
for i from 1 to nops(lefts) do
    start := lefts[i]:
    if i < nops(lefts) then 
       b:= lefts[i+1] - 1:
    else
       b:= n:
    fi:
    cycs:= [op(cycs), [op(start..b, pi)]]:
od:
    G:= CycToPer(cycs):
    
    G:
end:
    
perms := permute(7);
x1 := seq(evalb(AntiFoata(FoataA(pi)) = pi), pi in perms);
x2 := seq(evalb(FoataA(AntiFoata(pi)) = pi), pi in perms);
for x in x1 do
    if x = false then RETURN(false); end if;
end do;
#RETURN(true);
for y in x2 do
    if y = false then RETURN(false); end if;
end do;
#RETURN(true);

#true
#true

perms := permute(6);
x1 := seq(evalb(AntiFoata(FoataA(pi)) = pi), pi in perms);
x2 := seq(evalb(FoataA(AntiFoata(pi)) = pi), pi in perms);
for x in x1 do
    if x = false then RETURN(false); end if;
end do;
#RETURN(true);
for y in x2 do
    if y = false then RETURN(false); end if;
end do;
#RETURN(true);

#true 
#true

perms := permute(5);
x1 := seq(evalb(AntiFoata(FoataA(pi)) = pi), pi in perms);
x2 := seq(evalb(FoataA(AntiFoata(pi)) = pi), pi in perms);
for x in x1 do
    if x = false then RETURN(false); end if;
end do;
#RETURN(true);
for y in x2 do
    if y = false then RETURN(false); end if;
end do;
#RETURN(true);

#true 
#true


perms := permute(4);
x1 := seq(evalb(AntiFoata(FoataA(pi)) = pi), pi in perms);
x2 := seq(evalb(FoataA(AntiFoata(pi)) = pi), pi in perms);
for x in x1 do
    if x = false then RETURN(false); end if;
end do;
#RETURN(true);
for y in x2 do
    if y = false then RETURN(false); end if;
end do;
#RETURN(true);

#true 
#true


perms := permute(3);
x1 := seq(evalb(AntiFoata(FoataA(pi)) = pi), pi in perms);
x2 := seq(evalb(FoataA(AntiFoata(pi)) = pi), pi in perms);
for x in x1 do
    if x = false then RETURN(false); end if;
end do;
#RETURN(true);
for y in x2 do
    if y = false then RETURN(false); end if;
end do;
#RETURN(true);

#true 
#true


perms := permute(2);
x1 := seq(evalb(AntiFoata(FoataA(pi)) = pi), pi in perms);
x2 := seq(evalb(FoataA(AntiFoata(pi)) = pi), pi in perms);
for x in x1 do
    if x = false then RETURN(false); end if;
end do;
#RETURN(true);
for y in x2 do
    if y = false then RETURN(false); end if;
end do;
#RETURN(true);

#true 
#true

perms := permute(1);
x1 := seq(evalb(AntiFoata(FoataA(pi)) = pi), pi in perms);
x2 := seq(evalb(FoataA(AntiFoata(pi)) = pi), pi in perms);
for x in x1 do
    if x = false then RETURN(false); end if;
end do;
#RETURN(true);
for y in x2 do
    if y = false then RETURN(false); end if;
end do;
#RETURN(true);

#true 
#true


#AntiFoata(Foata(pi)) = pi and Foata(AntiFoata(pi))= pi for all permutations of size <= 7


#Problem 5

#xnk(n,k) = (1+xnk(0,k)^k+...+xnk(n-1,k)^k)/n
xnk:= proc(n,k) local i:
option remember:
if n = 0 then
   1:
else
   (1 + add(xnk(i,k)^k, i = 0..n-1))/n:
fi:
end:


#xnkC(n,k) clever
xnkC:= proc(n,k)
option remember:

if n = 0 then
   1:
elif n = 1 then
   2:
else
    ((n-1)*xnkC(n-1,k) + xnkC(n-1, k)^k)/n:
 fi:
 end:
   


#xnkP(n,k,p): modp
xnkP:= proc(n,k,p)
option remember:

if n = 0 then
   1 mod p:
elif n = 1 then
   2 mod p:
else
    ((n-1)*xnkC(n-1,k) + xnkC(n-1, k)^k)/n mod p:
 fi:
 end:
 
 
L := [];
for p to 15 do
    if isprime(p) then L := [op(L), ((p - 1)*xnkP(p - 1, 3, p) + xnkP(p - 1, 3, p)^3) mod p]; end if;
end do;
L;
 #                      [0, 0, 0, 0, 0, 0]

L := [];
for p to 15 do
    if isprime(p) then L := [op(L), ((p - 1)*xnkP(p - 1, 4, p) + xnkP(p - 1, 4, p)^4) mod p]; end if;
end do;
L;
#                       [0, 0, 0, 0, 0, 0]


#for k=3 and k=4, the first 15 terms are integers

#problems 6,7 optional
#my guess for #6 is 29 because thats when it started taking too much time to compute