print(` Version of Feb 6 2004`):
print(`This is 2-dimensional Wytoff game mex functions, A Maple package`):
print(`that guess the period patten for f(m,n) of the wytoff game.`):
print(`Written by Xiangdong Wen and Doron Zeilberger.`):
lprint(``):
print(`For general help, and a list of the available functions,`):
print(` type ezra();. For specific help type ezra(procedure_name) `):
lprint(``):

ezra:=proc()
if args=NULL then
print(`wytoff mex`):
print(`A Maple package that automatically guess the period patten for wytoff game`):
print(` and proof`):
print(`This package contains Procedures: `):
print(` mex,f,optmex,optf,guess,proof`):
print(` For specific help type ezra(procedure_name) `):
fi:
   
if nops([args])=1 and op(1,[args])=`mex` then
print(`mex is a simple mex(minimum exclude) function`):
print(` Example:mex([3,1,2])`):
fi:

if nops([args])=1 and op(1,[args])=`f` then
print(`f(a,b) is the wytoff function`):
print(`Example: f(3,3)`):
fi:

if nops([args])=1 and op(1,[args])=`optmex` then
print(`optmex(chain,from) is a optimized mex function `):
print(`it returns a value bigger or equal to 'from' and the value is not in chain`):
print(` Example:optmex([m+3,m+1,m+2],m-1)`):
fi:

if nops([args])=1 and op(1,[args])=`optf` then
print(`optf(a,b) is a optimized wytoff function. `):
print(`Example: optf(3,3)`):
fi:

if nops([args])=1 and op(1,[args])=`guess` then
print(`guess(chain,symbol):using the symbol guess the period patten of the chain. `):
print(`Example: guess([seq(optf(i,2),i=0..1000)],m):`):
fi:

if nops([args])=1 and op(1,[args])=`proof` then
print(`prove the guessed chain is true or not`):

print(`Example: proof(2)`):
fi:

end:





















mex:=proc(s)local i,j,k;
for i from 0 to max(op(s)) do
if member(i,{op(s)}) then:else  
return i;
fi:od:
return max(op(s))+1;
end:

f:=proc(a,b) option remember:local i,j,k,children;
 if a=0 then return b;fi:
 if b=0 then return a;fi:
 children:=[];
 for i from 0 to a-1 do
 children:=[op(children),f(i,b)];
 od:
 for i from 0 to b-1 do
 children:=[op(children),f(a,i)];
 od:
 for i from 1 to min(a,b) do
 children:=[op(children),f(a-i,b-i)];
 od:
 return mex(children):
 end:


optmex:=proc(s,m)local i,j,k;

if nops(s)=0 then return m; fi:
for i from 0 to max(op(s))-m do
if member(i+m,{op(s)}) then:else  
return i+m;
fi:
od:

return max(op(s))+1;
end:

optf:=proc(a,b) option remember:local i,j,k,children,begin,begin2;
 if a=0 then return b;fi:
 if b=0 then return a;fi:
 children:=[];
 begin:=0;
 if a-2*b-1 >0 then begin:=a-2*b-1;fi:
 begin2:=0;
 if a-3*b-1 >0 then begin2:=a-3*b-1;fi:
 
 for i from begin2 to a-1 do
 children:=[op(children),optf(i,b)];
 od:
 for i from 0 to b-1 do
 children:=[op(children),optf(a,i)];
 od:
 for i from 1 to min(a,b) do
 children:=[op(children),optf(a-i,b-i)];
 od:
 return optmex(children,begin):
 end:

expandchain:=proc(ch,n) local i,j,k,chain,p;
p:=nops(ch);
chain:=[]:

for i from 0 to n-1 do
chain:=[op(chain),ch[i-p*floor(i/p)+1]+p*floor(i/p)    ]:
od:
chain:
end:



guess:=proc(chain,symbol) local i,j,k,num,s,half,form,t;
num:=nops(chain);
half:=floor(num/2):
for i from half+1 to num do
k:=i-half;
if(chain[half]+k=chain[i]) then
 
  s:=0;
  for j from half to num-k do 
    if chain[j]+k <> chain[j+k] then
    s:=1;
    fi:
    if s=1 then break; fi:
  od:

  if s=0 then
   t:=floor(half/k)*k+1:
   form:=[]:
   for j from t to t+k-1 do
   form:=[op(form),symbol+chain[j]-t]:
   od:
  fi:


  if s=0 then 
  for j from half to 1 by -1 do
    if chain[j]+k <>chain[j+k] then
	return([k,j+1,form]);
    fi: 
  od:
  return([k,1,form]);	
  fi: 
fi:
od:
return([-1]):
end:

symbolchainf:=proc(a,n,chain,symbol) option remember:local i,j,k,ch;
ch:=guess(chain,symbol)[3]:
expandchain(ch,n);
end:

symbolf:=proc(a,n,symbol) option remember: local i,j,k,ch;
ch:=[seq(optf(i,a),i=0..1000)];
symbolchainf(a,n,ch,symbol):
end:

symbolelemf:=proc(a,b,symbol) option remember: local i,j,k,ch;
ch:=[seq(optf(i,a),i=0..1000)];
symbolchainf(a,b,ch,symbol)[b]:
end:


proof:=proc(b) local i,j,k,gue,p,prf,m,ch,guessedchain;

#p:=nops(chain);
ch:=guess([seq(optf(i,b),i=0..1000)],m):
p:=ch[1]:
guessedchain:=expandchain(ch[3],2*p+3*b);

prf:=true:
for i from 1 to p do
if symbolmex(b,3*b+i,m)+p<>symbolmex(b,3*b+i+p,m)then prf:=false; fi:
od:
ch,prf:
end:

symbolmex:=proc(b,a,sym)option remember: local i,j,k,elem;
elem:=[];
for i from 1 to a-1 do
elem:=[op(elem),symbolelemf(b,i,sym)]:
od:
elem;
for i from 0 to b-1 do
elem:=[op(elem),symbolelemf(i,a,sym)]:
od:
elem;
for i from 1 to min(a-1,b) do
elem:=[op(elem),symbolelemf(b-i,a-i,sym)]:
od:
elem;
optmex(elem,sym+a-1-2*b-1):
end: