#OK to post homework
#Yuxuan Yang, April 9th, Assignment 20
with(combinat):


#1
ConjLP:=proc(R) local M,C,i,L:
L:=LP(10000,R):
for M from 2 to 9999 do
C:=convert(L mod M,set):
if nops(C)< M then 
 RETURN([M,C]):
fi:
od:
RETURN(FAIL):
end:

#2
ProveLP:=proc(R,M,C) local i,j,S:
if not 0 in C then 
 RETURN(FAIL):
fi:
S:={}:
for i in R do
 for j in C do
  if j-i mod M in C then 
   RETURN(FAIL):
  fi:
  S:=S union {i+j mod M}:
 od:
od:
if nops(S union C)<>M then
RETURN(FAIL):
fi:
print(`proved`):
end:

#3
Nim:=proc(N) local i,j,S,Ns:

option remember:
if sort(N)<>N then 
 print(`we are working on`, sort(N),`instead of `,N):
fi:
S:={}:
Ns:=sort(N):
for i from 1 to nops(Ns) do
 for j from 1 to Ns[i] do
  Ns:=sort(N):
  Ns[i]:=Ns[i]-j:
  Ns:=sort(Ns):
  if Nim(Ns)[1]=0 then
   S:=S union {[i,j]}:
  fi:
 od:
od:
if S={} then
 0,S:
else
 1,S:
fi:

end:

#4
NimL:=proc(k,N) local S,s:
S:={}:
for s in wdkN(k,N) do
 if Nim(s)[1]=0 then 
  S:=S union {s}:
 fi:
od:
S:
end:

wdkN:=proc(k,N) local i,s,S,j:
if k=1 then 
RETURN({seq([i],i=0..N)}):
fi:
S:={}:
for s in wdkN(k-1,N) do
 for j from 0 to s[1] do
  S:=S union {[j,op(s)]}:
 od:
od:
S:
end:

#5
#Unfortunately, I have the answer in my mind, so I don't have the chance to discover it again.

#6
Nim2V:=proc(a,b) local i,j,S:
option remember:
S:={}:
for i from 1 to a do
 if Nim2V(a-i,b)[1]=0 then
  S:=S union {[i,0]}:
 fi:
od:
for j from 1 to b do
 if Nim2V(a,b-j)[1]=0 then
  S:=S union {[0,j]}:
 fi:
od:
for i from 1 to min([a,b]) do
 if Nim2V(a-i,b-i)[1]=0 then
  S:=S union {[i,i]}:
 fi:
od:
if S={} then
 0,S:
else
 1,S:
fi:
end:

#7
Nim2VL:=proc(N) local S,s:
S:={}:
for s in wdkN(2,N) do
 if Nim2V(s[1],s[2])[1]=0 then 
  S:=S union {s}:
 fi:
od:
S:
end:

#8
#a_n:=A188035
#b_n:=A188036
#the lp is [0,0] and [a_n,b_n].
#explicit formula can be found at A188034


#Maple code for Lecture 20
#April 4, 2022, C20.txt
Help20:=proc(): print(` P12(n), PR(n,R), LP(N,R) `):end:

#PILE Of pennies , so the STATE of the game is the "number of pennies"
#LEGAL MOVE: REMOVE ONE OR TWO PENNIES
#YOU LOST IF there is no pennies: 
#
#******
#***
#WE WANT A FUNCTION THAT INPUTS n and outputs 1 if is a winning position and 0 if it a losing position
#ALSO THE WINNING MOVE
#
#P12(n): 1-pile Nim with {1,2} removal
P12:=proc(n) local i,S:
option remember:



S:={}:

for i from 1 to min(2,n) do
 if P12(n-i)[1]=0 then
   S:=S union {i}:
 fi:
od:
if S={} then
 0,S:
else
 1,S:
fi:

end:

#PR(n,R): Inputs a pos. integer n and a set of POSITIVE integers R
#outputs 0,{} or 1,S where 0 means losing and S is the set of winning moves
PR:=proc(n,R) local i,S:
option remember:


S:={}:

for i in R do
 if i<=n and PR(n-i,R)[1]=0 then
   S:=S union {i}:
 fi:
od:
if S={} then
 0,S:
else
 1,S:
fi:

end:
#
#LP(N,R): Inputs a pos. integer N and a removal set R outputs the
#list of losing positions <=N
LP:=proc(N,R) local L,i:
L:=[]:
for i from 1 to N do
 if PR(i,R)[1]=0 then
  L:=[op(L),i]:
 fi:
od:
L:
end: