######################################################################
##UlPer.txt:                                                         #
#Save this file as UlPer.txt                :                        #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read `UlPer.txt`: <Enter>                          #
##Then follow the instructions given there                           #
##Written by Yukun Yao, and                                          #
##Written by Doron Zeilberger, Rutgers University ,                  #
#[yao,zeilberg] at math dot rutgers dot edu                          #
######################################################################
 
#Created: Oct. 2019
 
print(`Created: Oct, 2019`):
print(` This is UlPer.txt  `):
print(`For using the Ultimate Periodicity Ansatz as applied to Nim-style games`):
print(`It accompanies the paper `):
print(` The Ultimate Periodicity Ansatz `):
print(`by Yukun Yao and Doron Zeilberger`):
print(`and also available from his website`):
print(``):
print(`Please report bugs to zeilberg at math dot rutgers dot edu`):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.rutgers.edu/~zeilberg/  .`):

print(`-----------------------------------`):
 print(`For a list of the MAIN procedures type ezra();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):

print(`-----------------------------------`):

print(`-----------------------------------`):
 print(`For a list of the SUPPORTING procedures type ezra1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):

print(`-----------------------------------`):


print(`-----------------------------------`):
 print(`For a list of the Story procedures, type ezraSt();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):

print(`-----------------------------------`):


print(`-----------------------------------`):
 print(`For a list of the One-Pile Take Away type ezraP1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):

print(`-----------------------------------`):


with(combinat):




ezraSt:=proc()

if args=NULL then
 print(` The Story procedures are: G1Pv`):
 print( `  `):
else
ezra(args):
fi:

end:

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are:`):
 print( `  mex,  Nimian00, Nimian01,Nimian10,Nimian11, PL1, SeqTA, UP1`):
else
ezra(args):
fi:

end:

ezraP1:=proc()

if args=NULL then
 print(` The procedures about one pile are: G1P, G1P1, G1Pg, `):
 print( `  `):
else
ezra(args):
fi:

end:


ezra:=proc()

if args=NULL then
 print(`The main procedures are: `):
 print(` D00, gN, PL, UP, wG, wGpairs, wGpairsRes,wN, wNres  `):


elif nops([args])=1 and op(1,[args])=D00 then
print(`D00(L): Given a sequence L, finds the sequence L[2*i1]-2*L[i]`):


elif nops([args])=1 and op(1,[args])=G1P then
print(`G1P(S,N): inputs a finite set S of POSITIVE integers, outputs the list of the Grundy function of the take-away game where`):
print(`the legal moves are taking a member of S, for i from 1 to N. Try:`):
print(`G1P({1,2},10);`):

elif nops([args])=1 and op(1,[args])=G1Pg then
print(`G1Pg(S,N): inputs a finite set S of POSITIVE integers, outputs the initial segement and the ultimate period all checked`):
print(`the legal moves are taking a member of S, for i from 1 to N. Try:`):
print(`G1Pg({1,2},30);`):

elif nops([args])=1 and op(1,[args])=G1Pv then
print(`G1Pv(S,N): inputs a finite set S of POSITIVE integers, outputs a theorem about the Grundy function of `):
print(` a 1-pile take-away game. It uses the first N values`):
print(`the legal moves are taking a member of S, for i from 1 to N. Try:`):
print(`G1Pv({1,2},100);`):

elif nops([args])=1 and op(1,[args])=G1P1 then
print(`G1P1(S,i): inputs a finite set S of POSITIVE integers, outputs the Grundy function of local i, of the take-away game where`):
print(`the legal moves are taking a member of S. Try:`):
print(`G1P1({1,2},10);`):

elif nops([args])=1 and op(1,[args])=gN then
print(`gN(a,b,s): Generalized Grundy of two-pile Nim with gN(0,0)=s`):


elif nops([args])=1 and op(1,[args])=mex then
print(`mex(S): the smallest pos. integer NOT in the set of positive integers, S. Try:`):
print(`mex({0,1,2,5,6});`):

elif nops([args])=1 and op(1,[args])=Nimian00 then
print(`Nimian00(F,a1,b1): Nimian00(F,a1,b1): inputs a function F(a,b) of defined on the first discrete quadrant and a pair`):
print(` of pos. integers a1, b1, outputs`):
print(`F(2*a1,2*b1)-2*F(a1,b1). Try:`):
print(`Nimian00((a,b)->gN(a,b,0),5,7);`):

elif nops([args])=1 and op(1,[args])=Nimian10 then
print(`Nimian10(F,a1,b1): Nimian00(F,a1,b1): inputs a function F(a,b) of defined on the first discrete quadrant and a pair`):
print(` of pos. integers a1, b1, outputs`):
print(`F(2*a1+1,2*b1)-2*F(a1,b1)-1. Try:`):
print(`Nimian10((a,b)->gN(a,b,0),5,7);`):

elif nops([args])=1 and op(1,[args])=Nimian01 then
print(`Nimian01(F,a1,b1): Nimian00(F,a1,b1): inputs a function F(a,b) of defined on the first discrete quadrant and a pair`):
print(` of pos. integers a1, b1, outputs`):
print(`F(2*a1,2*b1+1)-2*F(a1,b1)-1. Try:`):
print(`Nimian01((a,b)->gN(a,b,0),5,7);`):

elif nops([args])=1 and op(1,[args])=Nimian11 then
print(`Nimian11(F,a1,b1): Nimian00(F,a1,b1): inputs a function F(a,b) of defined on the first discrete quadrant and a pair`):
print(` of pos. integers a1, b1, outputs`):
print(`F(2*a1+1,2*b1+1)-2*F(a1,b1). Try:`):
print(`Nimian11((a,b)->gN(a,b,0),5,7);`):

elif nops([args])=1 and op(1,[args])=PL then
print(`PL(B,s,K): sequence of ultimate period-lengths of gN(a,b,s)-a for`):
print(`b from 1 to B`):
print(`trying up to K. For example, try:`):
print(`PL(10,2,300);`):

elif nops([args])=1 and op(1,[args])=PL1 then
print(`PL1(b,s,K): the ultimate period-length of gN(a,b,s)-a for`):
print(`trying up to K. For example, try:`):
print(`PL1(6,2,300);`):

elif nops([args])=1 and op(1,[args])=UP then
print(`UP(L): Given a sequence L, decides whether it is`):
print(`ultimately periodic, and`):
print(`returns the beginning and the periodic part.`):
print(`For example, try: UP([3,1,4,2,4,2,4,2,4,2,4,2]);`):
print(``):


elif nops([args])=1 and op(1,[args])=UP1 then
print(`UP1(L,p): is the sequence L ultimately periodic of period p?`):
print(`returns the beginning and the periodic part`):
print(`For example, try: UP1([3,1,4,2,4,2,4,2,4,2,4,2],2);`):


elif nops([args])=1 and op(1,[args])=wG then
print(`wG(i,s): the unique j>=0 such that wN(i,j)=s. Try:`):
print(`wG(10,1);`):

elif nops([args])=1 and op(1,[args])=wGpairs then
print(`wGPairs(s,K): all the pairs [i,j] with i<=j such that the Grundy-Wythoff function is s.`):
print(`Try:`):
print(`wGpairs(0,20);`):

elif nops([args])=1 and op(1,[args])=wGpairsRes then
print(`wGPairsRes(s,r,K): all the pairs [i,j] with i<=j such that the Grundy function of the resticted r-Wythoff function is s.`):
print(`Try:`):
print(`wGpairsRes(0,1,20);`):

elif nops([args])=1 and op(1,[args])=wN then
print(`wN(a,b): Grundy function for Wythoff's game . Try:`):
print(`wN(10,11);`):

elif nops([args])=1 and op(1,[args])=wNres then
print(`wNres(a,b,r): Grundy function for the restricted Wythoff's game where one can only remove up to r pennies from both piles. Try:`):
print(`wNres(10,11,1);`):

else
print(`There is no ezra for`,args):
fi:
 
end:





##############Start Detecting ultimate periodicity


#Shrink1(L): normalizes L=[L1,L2]
Shrink1:=proc(L) local L1,L2:
L1:=L[1]: L2:=L[2]:
if L1=[] then
  RETURN(L):
fi:

if L1[nops(L1)]=L2[nops(L2)] then
  RETURN([[op(1..nops(L1)-1,L1)],[L2[nops(L2)],op(1..nops(L2)-1,L2)]]):
else
  RETURN(L):
fi:
end:

Shrink:=proc(L) local L1:

L1:=L:

while L1<>Shrink1(L1) do
L1:=Shrink1(L1):
od:
L1:
end:

#UP1(L,p): is the sequence L ultimately periodic of period p?
#returns the beginning and the periodic part
#For example, try: UP1([3,1,4,2,4,2,4,2,4,2,4,2],2);
UP1:=proc(L,p) local i,m,gu,mu,i1,gu1,gu2:


m:=nops(L):
 if m-2*p+1<1 then
 print(`Too short`):
 RETURN(FAIL):
fi:

m:=nops(L):

if L[m]<>L[m-p] then 
 RETURN(FAIL):
fi:

if L[m-1]<>L[m-1-p] then 
 RETURN(FAIL):
fi:

if L[m-2]<>L[m-2-p] then 
 RETURN(FAIL):
fi:

if L[m-3]<>L[m-3-p] then 
 RETURN(FAIL):
fi:


if not [op(m-p+1..m,L)]=[op(m-2*p+1..m-p,L)] then
 RETURN(FAIL):
fi:


gu2:=[op(m-p+1..m,L)]:


for i from 1 while [op(i..i+p-1,L)]<>gu2 do od:

gu1:=[op(1..i-1,L)]:

gu:=[gu1,gu2]:
mu:=[op(gu1),
 seq(op(gu2),i1=1..trunc((m-nops(gu1)) /p) )
    ]:

     if mu<>[op(1..nops(mu),L)] then

       FAIL:
      else
       Shrink(gu):
      fi:

end:





#UP(L): Given a sequence L, decides whether it is
#ultimately periodic, and
#returns the beginning and the periodic part
#For example, try: UP([3,1,4,2,4,2,4,2,4,2,4,2]);
UP:=proc(L) local p,m,gu:

m:=nops(L):

for p from 1 to trunc((m-10)/2) do
 gu:=UP1(L,p):

  if gu<>FAIL then
    RETURN(gu):
  fi:
od:


FAIL:

end:







####


mex:=proc(A)
local i:
for i from 0 while member(i,A) do od:
i:
end:




#gN(a,b,s): Generalized Grundy of two-pile Nim with gN(0,0)=s
gN:=proc(a,b,s) local i:
option remember:
if a=0 and b=0 then
 RETURN(s):
else
mex({seq(gN(a-i,b,s),i=1..a),seq(gN(a,b-i,s),i=1..b)}):
fi:

end:



#D00(L): Given a sequence L, finds the sequence L[2*i1]-2*L[i]
D00:=proc(L) local i:
[seq(L[2*i]-2*L[i],i=1..nops(L)/2)]:
end:


#PL1(b,s,K): the ultimate period-length of gN(a,b,s)-a for
#trying up to K. For example, try:
#PL1(6,2,300);
PL1:=proc(b,s,K) local gu,a,lu:
gu:=[seq(gN(a,b,s)-a,a=1..K)]:
lu:=UP(gu):
if lu=FAIL then
 RETURN(FAIL):
else
 RETURN(nops(lu[2])):
fi:
end:



#PL(B,s,K): the sequence ultimate period-length of gN(a,b,s)-a for
#for b from 1 to B, or shorter, as soon as it fails
#trying up to K. For example, try:
#PL(10,2,1000);
PL:=proc(B,s,K) local b,gu,lu:
gu:=[]:
for b from 1 to B do
lu:=PL1(b,s,K):
if lu=FAIL then
  RETURN(gu):
else
 gu:=[op(gu),lu]:
fi:
od:

gu:
end:


#wN(a,b): Grundy function for Wythoff's game . Try:
#wN(10,11);
wN:=proc(a,b) local i:
option remember:
if a=0 and b=0 then
 RETURN(0):
else
mex({seq(wN(a-i,b),i=1..a),seq(wN(a,b-i),i=1..b), seq(wN(a-i,b-i),i=1..min(a,b)) }):
fi:

end:


#wG(i,s): the unique j>=0 such that wN(i,j)=s. Try:
#wG(10,1);
wG:=proc(i,s) local j:
for j from 0 while wN(i,j)<>s do od:
j:
end:

#wGres(i,r,s): the unique j>=0 such that wNres(i,j,r)=s. Try:
#wGres(10,1);
wGres:=proc(i,r,s) local j:
for j from 0 while wNres(i,j,r)<>s do od:
j:
end:




#wGpairs(s,K): all the pairs [i,j] with i<=j such that the Grundy-Wythoff function of the Wythoff game is s.
#Try:
#wGpairs(0,20);
wGpairs:=proc(s,K) local i,j,gu:
gu:=[]:

for i from 0 to K do
 j:=wG(i,s):
 if j>=i then
   gu:=[op(gu),[i,j]]:
 fi:
od:

gu:

end:


#wGpairsRes(s,r,K): all the pairs [i,j] with i<=j such that the Grundy function of the resticted r-Wythoff function of the Wythoff game is s.
#Try:
#wGpairsRes(0,1,20);
wGpairsRes:=proc(s,r,K) local i,j,gu:
gu:=[]:

for i from 0 to K do
 j:=wGres(i,r,s):
 if j>=i then
   gu:=[op(gu),[i,j]]:
 fi:
od:

gu:

end:

#G1P1(S,i): inputs a finite set S of POSITIVE integers, outputs the Grundy function of local i, of the take-away game where
#the legal moves are taking a member of S. Try:
#G1P1({1,2},10);
G1P1:=proc(S,i) local S1,i1:
option remember:
if i=0 then
 RETURN(0):
else
 S1:=S intersect {seq(i1,i1=1..i)}:
RETURN(mex({seq(G1P1(S,i-i1),i1 in S1)})):
fi:
end:



#G1P(S,N): inputs a finite set S of POSITIVE integers, outputs the list of the Grundy function of the take-away game where
#the legal moves are taking a member of S, for i from 1 to N. Try:
#G1P({1,2},10);
G1P:=proc(S,N) local i:
[seq(G1P1(S,i),i=1..N)]:
end:

#G1Pg(S,N): inputs a finite set S of POSITIVE integers, outputs the initial segement and the ultimate period all checked
#the legal moves are taking a member of S, for i from 1 to N. Try:
#G1Pg({1,2},10);
G1Pg:=proc(S,N) local gu,mu1,ka,mu,i,s,n1:
gu:=G1P(S,N):
mu:=UP(gu):

if mu=FAIL then
 print(`Make`, N, ` bigger `):
 RETURN(FAIL):
fi:

mu1:=[op(mu[1])]:

ka:=3*max(op(S))+nops(mu[2]):
ka:=ka/nops(mu[2])+1:
ka:=trunc(ka):

for i from 1 to ka do
mu1:=[op(mu1),op(mu[2])]:
od:

if {seq(mex({seq(mu1[n1-s], s in S)})-mu1[n1],n1=nops(mu1)-nops(mu[2])..nops(mu1))}<>{0} then
 print(`Make`, N, ` bigger `):
 RETURN(FAIL):
fi:
 
mu:
end:




#G1Pv(S,N): inputs a finite set S of POSITIVE integers, and a positive
#integer N, outputs a theorem about the Grundy function of the take-away game where
#the legal moves are taking a member of S, using data gathered from the first N values. Try:
#G1Pc({1,2},100);
G1Pv:=proc(S,N) local gu,n,m,i,s,Mex:

gu:=G1Pg(S,N):

if gu=FAIL then
 print(` Make `, N, `bigger `):
 RETURN(FAIL):
fi:

print(`The Grundy function of the One-Pile Take-Away Game with Moves`, S):
print(``):
print(``):
print(`Consider the 1-Pile game, where playes take turns removing pennies from a pile with, until there are no pennies left.`):
print(`At its turn, a player can remove a number of pennies from the set`):
print(S):

print(`The person that has no legal move is the loser.`):
print(`Let G(n) be the Sprague-Grundy function of that take-away game.`):
print(``):
print(`We have, of course,G(0)=0`):

for i from 1 to nops(gu[1]) do
G(i)=gu[1][i]:
od:

print(`We have, for every non-negative integer, m`):

for i from 1 to nops(gu[2]) do
 print(G(nops(gu[1])+i+nops(gu[2])*m)=gu[2][i]):
od:

print(``):
print(`Proof: It is readily checked that the right hand side sequence satisfies the recurrence defining G(n)`):
print(`Here Mex(S), is the smallest non-negative integer NOT in the set S`):
print(``):
print(G(n)=Mex({seq(G(n-s), s in S)})):
print(``):
print(`QED.`):
print(``):
end:



#Nimian00(F,a1,b1): Nimian00(F,a1,b1): inputs a function F(a,b) of defined on the first discrete quadrant and a pair
# of pos. integers a1, b1, outputs
#F(2*a1,2*b1)-2*F(a1,b1). Try:
#Nimian00((a,b)->gN(a,b,0),5,7);
Nimian00:=proc(F,a1,b1)
F(2*a1,2*b1)-2*F(a1,b1):
end:

#Nimian10(F,a1,b1): Nimian10(F,a1,b1): inputs a function F(a,b) of defined on the first discrete quadrant and a pair
# of pos. integers a1, b1, outputs
#F(2*a1+1,2*b1)-2*F(a1,b1)-1. Try:
#Nimian10((a,b)->gN(a,b,0),5,7);
Nimian10:=proc(F,a1,b1)
F(2*a1+1,2*b1)-2*F(a1,b1)-1:
end:

#Nimian01(F,a1,b1): Nimian01(F,a1,b1): inputs a function F(a,b) of defined on the first discrete quadrant and a pair
# of pos. integers a1, b1, outputs
#F(2*a1,2*b1+1)-2*F(a1,b1)-1. Try:
#Nimian01((a,b)->gN(a,b,0),5,7);
Nimian01:=proc(F,a1,b1)
F(2*a1,2*b1+1)-2*F(a1,b1)-1:
end:


#Nimian11(F,a1,b1): Nimian11(F,a1,b1): inputs a function F(a,b) of defined on the first discrete quadrant and a pair
# of pos. integers a1, b1, outputs
#F(2*a1+1,2*b1+1)-2*F(a1,b1). Try:
#Nimian11((a,b)->gN(a,b,0),5,7);
Nimian11:=proc(F,a1,b1)
F(2*a1+1,2*b1+1)-2*F(a1,b1):
end:




#wNres(a,b,r): Grundy function for the restricted Wythoff's game where one can only remove up to r pennies from both piles. Try:
#wNres(10,11,1);
wNres:=proc(a,b,r) local i:
option remember:
if a=0 and b=0 then
 RETURN(0):
else
mex({seq(wNres(a-i,b,r),i=1..a),seq(wNres(a,b-i,r),i=1..b), seq(wNres(a-i,b-i,r),i=1..min(a,b,r)) }):
fi:

end: