read ChompData: ###################################################################### ##BYRNES: Save this file as BYRNES. To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read BYRNES : # ##Then follow the instructions given there. # ## # ##Written by Doron Zeilberger, Rutgers University , # # zeilberg@math.rutgers.edu . # ###################################################################### #Created: June 3, 2003 #This version: June 5, 2015 (adding procedure Larson) #BYRNES: A Maple package to study 3-rowed chomp #Using an "instant winners" approach and #the "ultimately-periodic ansatz" inspired by Steven Byrnes #The Maple package accompanies the article #CHOMP, RECURRENCES, and CHAOS(?) by Doron Zeilberger #(dedicated to Saber Elaydi on his 60th birthday) #Please report bugs to zeilberg@math.rutgers.edu print(`Created: June 3, 2003.`): print(`This version: June 3, 2003 .`): lprint(``): print(`Written by Doron Zeilberger, zeilberg@math.rutgers.edu .`): lprint(``): print(`BYRNES: A Maple package to study 3-rowed Chomp,`): print(`using an "instant winners" approach and `): print(`the "ultimately-periodic ansatz" inspired by Steven Byrnes.`): print(`The Maple package accompanies the article`): print(` CHOMP, RECURRENCES, and CHAOS(?) `): print(`(dedicated to Saber Elaydi on his 60th birthday) .`): print(`Please report bugs to zeilberg@math.rutgers.edu . `): lprint(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/`): print(`For a list of the MAIN procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name);`): print(`For a list of ALL procedures type ezra1(); `): print(``): ezra:=proc() if args=NULL then print(`The MAIN FUNCTIONS are:`): print(` ChompLosers, ChompGrundy , DerSeq, Larson `): print(``): print(`The pre-computed data is`): print(` ChompLosers400, Grundy100_3, Grundy50_6 `); print(``): print(`For a list of all procedures type: ezra1(); `): print(``): print(`For help with any of these, type: ezra(Procedure_Name); `): print(`For example, for help with ChompLosers, type ezra(ChompLosers); `): fi: if nops([args])=1 and op(1,[args])=Adjust1 then print(`Adjust1(UP1,k): converts an Ultimately periodic sequence`): print(`UP1 to one in which the fixed part has length k if`): print(`it has length less than k to begin with`): print(`For example, try: Adjsut1([[1,2,3],[4,5]],4);`): fi: if nops([args])=1 and op(1,[args])=AllMoves then print(`AllMoves(POS): All moves from position [c,a,b] (i.e. 3^c2^a1^b)`): print(`(i.e. (c+a+b,c+a,a)). For example, try AllMoves([1,1,1]);`): fi: if nops([args])=1 and op(1,[args])=CheckChompGrundy then print(`CheckChompGrundy(N,G,L): Checks the validity of procdeure`): print(`ChompGrundy by comparing it to the raw data generated by`): print(`GrundyDirect up to L cells. For example, try`): print(`CheckChompGrundy(10,3,20)`): fi: if nops([args])=1 and op(1,[args])=ChompGrundy then print(`ChompGrundy(N,G): Given positive integers N and G,`): print(`outputs a list of lists LIST such that LIST[g+1][c+1] describes`): print(`the Chomp positions [c,a,b] (i.e. top row having a+b+c cells,`): print(`middle row b+c, and bottom row c cells) whose Spargue-Grundy`): print(`value equals g, given in ultimately-periodic notation [INI,Period]`): print(`such that the resulting sequence `): print(`[op(INI),op(Period),op(Period), ...]`): print(` is such that the (a+1)^th entry equals b.`): print(`For example try: ChompGrundy(10,3);`): fi: if nops([args])=1 and op(1,[args])=ChompLosers then print(`ChompLosers(L): The Losing table for c=0, ... , L `): print(`The input is a positive integer L, and the output is a list`): print(`of length L+1. `): print(`ChompLosers(L)[c+1] is a list of length 2, let's call it S `): print(`The meaning of S is as follows (it is the sequence B_c in the paper`): print(`If S[2]=[] then let T be the sequence S[1], otherwise, let`): print(`T be the infinite sequence S[1]S[2]S[2]S[2]..., where S[2] is `): print(`repeated ad infinitum`): print(`T[a+1] equals the unique b such that [c,a,b] is`): print(` a losing position in 3-rowed Chomp (using the bracket notation) `): print(` where [c,a,b] means the position with c+a+b squares in the top row`): print(`c+a in the middle row, and c in the bottom row`): print(``): print(`For example, try ChompLosers(10); `): fi: if nops([args])=1 and op(1,[args])=ChompLosers400 then print(`ChompLosers400; : The pre-computed Chomp series for 0<=c<=400`): print(`In other words, the output of ChompLosers(400); `): fi: if nops([args])=1 and op(1,[args])=DerSeq then print(`DerSeq(Resh): Given a Chomp sequence (output of Chomp, or `): print(`precomputed ChompLosers400)`): print(`finds two sequences `): print(`The first is those of c such that a winning move for 3^c is`): print(`of the form 3^c' 2^0 1^(c-c') (i.e. chomping from the middle row)`): print(`The second is those of c such that the winning move for 3^c is`): print(`of the form 3^c' 2^(c-c') 1^0 (i.e. chomping from the bottom row)`): print(`For example, try DerSeq(ChompLosers400);`): fi: if nops([args])=1 and op(1,[args])=DetectPeriod1 then print(`DetectPeriod1(Resh,P,R):Checks whether the last P*(R+1) entries`): print(`of the list Resh are periodic of period P`): fi: if nops([args])=1 and op(1,[args])=DetectPeriod then print(`DetectPeriod(Resh,R):Finds the period, or returns FAIL`): print(`that the last entries of the list obey to depth R`): fi: if nops([args])=1 and op(1,[args])=Grundy100_3 then print(`Grundy100_3; : The pre-computed output of ChompGrundy(100,3); `): fi: if nops([args])=1 and op(1,[args])=Grundy50_6 then print(`Grundy100_3; : The pre-computed output of ChompGrundy(50,6); `): fi: if nops([args])=1 and op(1,[args])=GrundyDirect then print(`GrundyDirect(L): The table of the Grundy function of all`): print(`[c,a,b] with c+a+b<=L`): print(`It inputs a positive integer, and outputs a list whose `): print(`(g+1)^th entry is the set of all Chomp positions [c,a,b], 3^c 2^a 1^b`): print(`(i.e. 3-rowed Chomp positions with c+a+b cells at the top row,`): print(` a+b at the middle row, and c cells at the bottm row), whose`): print(`Sprague-Grundy value equals g`): print(`It uses the naive (finite) definition, and its main function is`): print(`as an empirical check for ChompGrundy (cf CheckChompGrundy) `): print(``): print(`For example, try: GrundyDirect(20); `): fi: if nops([args])=1 and op(1,[args])=GrundyDirectNice then print(`GrundyDirectNice(L): The table of the Grundy function of all`): print(`[c,a,b] with c+a+b<=L, in nice (i.e. Ultimately Periodic) form`): print(`gotten from GrundyDirect `): print(`For example, try: GrundyDirectNice(20): `): fi: if nops([args])=1 and op(1,[args])=GuessPeriod then print(`GuessPeriod(Lis): guesses beginning and period of a list Lis`): fi: if nops([args])=1 and op(1,[args])=Ikhud then print(`Ikhud(UP1,UP2): The union of two Ultimately Periodic Sequences`): print(`of sets UP1 and UP2 for example, try `): print(`Ikhud([[{1,2},{3,4}],[{1,2},{5,6}]],[[{4,5}],[{3,4},{0,1},{2,3}]]);`): fi: if nops([args])=1 and op(1,[args])=InstWin1 then print(`InstWin1(LS,x): Given LS=[SeqF,SeqP]`): print(`Finds the instant winnes due to increasing the number of 3's by x`): print(`For example try: InstWin1([[2,3],[4,5]],3);`): fi: if nops([args])=1 and op(1,[args])=InstWin1a then print(`InstWin1a(Seq1,x): Instant winners due to the fixed part`): fi: if nops([args])=1 and op(1,[args])=InstWin1b then print(`InstWin1b(Seq1,k1,x): Instant winners due to the periodic part`): print(`If [c,k1+i+nops(Seq1)*L,Seq1[i+1]], i=0..nops(Seq1)-1, are losers`): print(`Then `): print(`[c+x,k2+i+nops(Seq2)*L,Seq2[i+1]], i=0..nops(Seq1)-1, are instant`): print(`winners `): print(`For example, try: InstWin1b([4,5],3,2); `): fi: if nops([args])=1 and op(1,[args])=Larson then print(`Larson(): (Added June 5, 2015, inspired by Craig Larson's conjecture),`): print(`outputs the sequence of the minimum of alpha-gamma amongs all Winning (P) positions with three rows where`): print(` [alpha,beta,gamma] denotes the position (alpha+beta+gamma,alpha+beta,alpha) in the usual notation `): print(` for alpha from 0 to 400 `): print(` According to Craig Larson's conjecture, it is >=-1, but has alpha gets bigger it seems to get bigger. `): print(`Added June 11, 2015: This conjecture has been proved by Craig Larson and Brian Kaperick`): print(`Try: Larson();`): fi: if nops([args])=1 and op(1,[args])=Losers then print(`Losers(IW): Given the Instant Winners in symbolic form`): print(`IW=[INI,[Period]], returns the losers in symbolic form`): print(`[INI,[Period]]`): fi: if nops([args])=1 and op(1,[args])=ProveLosers then print(`ProveLosers(LOS,IW): Given an Ultimately Periodic Instant`): print(`winners and a proposed Ultimately Periodic Losers proves`): print(`it rigorously`): fi: if nops([args])=1 and op(1,[args])=SpellOut then print(`SpellOut(Tab,L): using the table Tab spells out all the`): print(`losing positions [c,a,b] (3^c2^a1^b) with c+a+b<=L`): fi: if nops([args])=1 and op(1,[args])=WinningMoves then print(`WinningMoves(POS,Tab): All moves from position`): print(` [c,a,b] (i.e. 3^c2^a1^b)`): print(`(i.e. (c+a+b,c+a,a)). For example, try `): print(` WinningMoves([1,1,1],ChompLosers400);`): fi: end: ezra1:=proc() if args=NULL then print(`Contains the following procedures: Adjust1, AllMoves, `): print(` CheckChompGrundy, ChompOld, ChompLosers, ChompGrundy `): print(` ChompLosers400, DerSeq`): print(` DetectPeriod, GrundyDirect, GrundyDirectNice, GuessPeriod,`): print(` Ikhud, InstWin1, InstWin1a, InstWin1b,`): print(` Losers, LosersOneStep, ProveLosers, SpellOut, WinningMoves`): print(``): print(`For help with any of these, type: ezra(Procedure_Name); `): print(`For example, for help with GrundyDirect, type ezra(GrundyDirect); `): else ezra(args): fi: end: #GuessPeriod(Lis): Given a list, guesses an ultimate period GuessPeriod:=proc(Lis) local s0,p,n,i,j,gu: n:=nops(Lis)-4: for s0 from 1 to trunc(n/3) do for p from 1 to trunc((n-s0)/3) do if {seq(nops({seq(Lis[s0+p*i+j],i=0..trunc((n-j-s0)/p))}),j=1..p)}={1} then gu:=[[op(1..s0,Lis)],[op(s0+1..s0+p,Lis)]]: if nops(gu[1])=1 and nops(gu[2])>=1 and gu[1][1]=gu[2][1] then gu:=[[],gu[2]]: fi: RETURN(gu): fi: od: od: FAIL: end: #Expand1(IW,L): Given a symbolic pair, expands it #to the first L terms Expand1:=proc(IW,L) local i,gu: if IW[2]=[] then RETURN(IW[1]): fi: gu:=IW[1]: for i from 1 to trunc((L-nops(IW[1]))/nops(IW[2]))+1 do gu:=[op(gu),op(IW[2])]: od: [op(1..L,gu)]: end: mex:=proc(S) local i: for i from 0 while member(i,S) do od: i: end: #Losers(IW): Given the Instant Winners in symbolic form #IW=[INI,[Period]], returns the losers in symbolic form #[INI,[Period]] Losers:=proc(IWW) local i1,T,gu,kha,j,i,mu,j1,makom,YOMAN,IW: if IWW[1]=[] then IW:=[[IWW[2][1]],[op(2..nops(IWW[2]),IWW[2]),IWW[2][1]]]: else IW:=IWW: fi: T:=max(seq(op(IW[1][i1]),i1=1..nops(IW[1])), seq(op(IW[2][i1]),i1=1..nops(IW[2])))+2: YOMAN:=[]: mu:=[]: for i from 1 to nops(IW[1]) do kha:=IW[1][i]: for j from 1 to min(T,i)-1 do if mu[i-j]-j>=0 then kha:=kha union {mu[i-j]-j}: fi: od: YOMAN:=[op(YOMAN),kha]: mu:=[op(mu),mex(kha)]: #print(mu,YOMAN): if mu[nops(mu)]=0 then RETURN([mu,[]]): fi: od: for i from 0 do for j1 from 1 to nops(IW[2]) do: kha:=IW[2][j1]: makom:=nops(IW[1])+i*nops(IW[2])+j1: for j from 1 to min(T, makom)-1 do if mu[makom-j]-j>=0 then kha:=kha union {mu[makom-j]-j}: fi: od: if mu[nops(mu)]=0 then RETURN([mu,[]]): fi: YOMAN:=[op(YOMAN),kha]: mu:=[op(mu),mex(kha)]: if DetectPeriod(YOMAN,3)<>FAIL and DetectPeriod(mu,3)<>FAIL then if GuessPeriod(mu)<>FAIL then RETURN(GuessPeriod(mu)): fi: fi: od: od: end: Shrink1:=proc(Resh) if Resh[1]=[] then Resh: elif nops(Resh[1])>=nops(Resh[2]) and [op(nops(Resh[1])-nops(Resh[2])+1..nops(Resh[1]),Resh[1])]=Resh[2] then [ [op(1..nops(Resh[1])-nops(Resh[2]),Resh[1])],Resh[2]]: else Resh: fi: end: Shrink:=proc(Resh) local Resh1,Resh2: Resh1:=Resh: Resh2:=Shrink1(Resh1): while Resh2<>Resh1 do Resh1:=Resh2: Resh2:=Shrink1(Resh2): od: Resh2: end: InstWin1a:=proc(Seq1,x) local b0,mu,i,K: if Seq1=[] then RETURN([[],[{}]]): fi: b0:=Seq1[1]: K:=max(b0-x,nops(Seq1)-1): for i from 0 to K do mu[i]:={}: od: for i from 0 to b0-x do mu[i]:=mu[i] union {b0-x-i}: od: for i from x to nops(Seq1)-1 do mu[i-x]:=mu[i-x] union {Seq1[i+1]}: od: mu:=[seq(mu[i],i=0..K)]: for i from 1 to nops(mu) while mu[i]<>{} do od: [[op(1..i-1,mu)],[{}]]: end: #InstWin1b(Seq1,k1,x): If [c,k1+i+nops(Seq1)*L,Seq1[i+1]],i=0..nops(Seq)-1 #is a loser finds the sequence Seq2 and an integer #k1 such that [c+x,k2+i+nops(Seq2)*L,Seq2[i+1]], i=0..nops(Seq)-1 # is an instant winner InstWin1b:=proc(Seq1,k1,x) local mu,gu,R,i,L,k2: R:=nops(Seq1): if R=0 then RETURN([[],[{}]]): fi: gu:={}: for i from 0 to R-1 do for L from 0 while k1+i+R*L-x<0 do od: mu[k1+i+R*L-x]:=Seq1[i+1]: gu:=gu union {k1+i+R*L-x} od: k2:=min(op(gu)): [[{}$k2],[seq({mu[k2+i]},i=0..R-1)]]: end: InstWin1Old:=proc(LS,x) local LS1: if LS[1]=[] and LS[2]<>[] then LS1:=[[LS[2][1]],[op(2..nops(LS[2]),LS[2]),LS[2][1]]]: else LS1:=LS: fi: Ikhud(InstWin1a(LS1[1],x),InstWin1b(LS1[2],nops(LS1[1]),x)): end: #Adjust1(UP1,k): converts an Ultimately periodic sequence #UP1 to one in which the fixed part has length k if #it has length less than k to begin with #For example, try: Adjsut1([[1,2,3],[4,5]],4); Adjust1:=proc(UP1,k) local gu,lu,Newgu,Newlu,i: gu:=UP1[1]: lu:=UP1[2]: if k<=nops(gu) then RETURN(UP1): fi: Newgu:=gu: Newlu:=lu: for i from nops(gu)+1 to k do Newgu:=[op(Newgu),Newlu[1]]: Newlu:=[op(2..nops(Newlu),Newlu),Newlu[1]]: od: [Newgu,Newlu]: end: #Adjust2(UP1,p): Given an ultimately periodic sequence #expands the periodic part to be p times as large #for example try Adjust2([[1,4],[6,5]],4); Adjust2:=proc(UP1,p) local gu,lu,i,mu: gu:=UP1[1]: lu:=UP1[2]: mu:=[]: for i from 1 to p do mu:=[op(mu),op(lu)]: od: [gu,mu]: end: #Ikhud(UP1,UP2): The union of two Ultimately Periodic Sequences #of sets UP1 and UP2 for example, try #Ikhud([[{1,2},{3,4}],[{1,2},{5,6}]],[[{4,5}],[{3,4},{0,1},{2,3}]]); Ikhud:=proc(UP1,UP2) local UP1a,UP2a,k,gu1,lu1,k1,i: gu1:=UP1[1]: lu1:=UP2[1]: k:=max(nops(gu1),nops(lu1)): UP1a:=Adjust1(UP1,k):UP2a:=Adjust1(UP2,k): k1:=lcm(nops(UP1a[2]),nops(UP2a[2])): UP1a:=Adjust2(UP1a,k1/nops(UP1a[2])): UP2a:=Adjust2(UP2a,k1/nops(UP2a[2])): if not (nops(UP1a[1])=nops(UP2a[1]) and nops(UP1a[2])=nops(UP2a[2])) then ERROR(`Something is wromg`): fi: Shrink([[seq(UP1a[1][i] union UP2a[1][i],i=1..nops(UP1a[1]) )], [seq(UP1a[2][i] union UP2a[2][i],i=1..nops(UP1a[2]) )]]): end: #DetectPeriod1(Resh,P,R):Checks whether the last i*R entries #of the list Resh is periodic of period i DetectPeriod1:=proc(Resh,P,R) local i: if P*R>nops(Resh) then RETURN(false): fi: for i from 0 to P*(R-1) do if Resh[nops(Resh)-i]<>Resh[nops(Resh)-i-P] then RETURN(false): fi: od: true: end: #DetectPeriod(Resh,R):Finds the period, if any, #that the last entries of Resh obey, up to depth R DetectPeriod:=proc(Resh,R) local P: for P from 1 to trunc(nops(Resh)/R)-1 do if DetectPeriod1(Resh,P,R) then RETURN(P): fi: od: FAIL: end: InstWin1a1:=proc(Seq1,x) local b0,mu,i,K: if Seq1=[] then RETURN([[],[{}]]): fi: b0:=Seq1[1]: K:=max(b0-x,nops(Seq1)-1): for i from 0 to K do mu[i]:={}: od: for i from 0 to b0-x do mu[i]:=mu[i] union {b0-x-i}: od: mu:=[seq(mu[i],i=0..K)]: for i from 1 to nops(mu) while mu[i]<>{} do od: [[op(1..i-1,mu)],[{}]]: end: InstWin1a2:=proc(Seq1,x) local b0,mu,i,K: if Seq1=[] then RETURN([[],[{}]]): fi: b0:=Seq1[1]: K:=max(b0-x,nops(Seq1)-1): for i from 0 to K do mu[i]:={}: od: for i from x to nops(Seq1)-1 do mu[i-x]:=mu[i-x] union {Seq1[i+1]}: od: mu:=[seq(mu[i],i=0..K)]: for i from 1 to nops(mu) while mu[i]<>{} do od: [[op(1..i-1,mu)],[{}]]: end: InstWin1:=proc(LS,x) local LS1: if LS[1]=[] and LS[2]<>[] then LS1:=[[LS[2][1]],[op(2..nops(LS[2]),LS[2]),LS[2][1]]]: else LS1:=LS: fi: InstWin1a1(LS1[1],x), Ikhud(InstWin1a2(LS1[1],x),InstWin1b(LS1[2],nops(LS1[1]),x)): end: OneLess1:=proc(S) local i,gu: gu:=S minus {0}: {seq(gu[i]-1,i=1..nops(gu))}: end: OneLess:=proc(Resh) local i: Shrink1([[seq(OneLess1(Resh[1][i]),i=1..nops(Resh[1])) ],Resh[2]]):end: ShiftLeft:=proc(Resh) if Resh=[[],[]] then RETURN(Resh): elif Resh[1]<>[] then [[op(2..nops(Resh[1]),Resh[1])],Resh[2]]: else [[],[op(2..nops(Resh[2]),Resh[2]),Resh[2][1]]]: fi: end: #ChompWithoutProof(N): like Chomp(N), but without proof ChompWithoutProof:=proc(N) local gu,mu,j,muK: gu:=[[[],[1]]]: mu:=InstWin1(gu[1],nops(gu)): for j from 1 to N do gu:=[op(gu),Losers(Ikhud(mu))]: muK:=InstWin1(gu[nops(gu)],1): mu:=Ikhud(OneLess(mu[1]),muK[1]),Ikhud(ShiftLeft(mu[2]),muK[2]): od: gu: end: Rosh:=proc(Resh): if Resh=[[],[]] then FAIL: elif Resh[1]=[] then Resh[2][1]: else Resh[1][1]: fi: end: #DerSeq(Resh): Given a Chomp sequence (output of Chomp, or precomputed CS400) #finds two sequences #The first is those of c such that a winning move for 3^c is #of the form 3^c' 2^0 1^(c-c') (i.e. chomping from the middle row) #The second is those of c such that the winning move for 3^c is #of the form 3^c' 2^(c-c') 1^0 (i.e. chomping from the bottom row) #For example, try DerSeq(ChompLosers400); DerSeq:=proc(Resh) local mu1,mu2,i: mu1:=[]: mu2:=[]: for i from 0 to nops(Resh)-1 do mu1:=[op(mu1),Rosh(Resh[i+1])+i]: if Resh[i+1][2]=[] then mu2:=[op(mu2),nops(Resh[i+1][1])-1+i]: fi: od: mu1,mu2: end: #ProveLosers(LOS,IW): Given an Ultimately Periodic Instant #winners and a proposed Ultimately Periodic Losers proves #it rigorously ProveLosers:=proc(LOS,IW) local T,x0,P,LOS1,IW1,i,j,lu: T:=max(op(LOS[1]),op(LOS[2])): P:=lcm(nops(LOS[2]),nops(IW[2])): x0:=max(nops(IW[1]),nops(LOS[1]))+T+P: IW1:=IW[1]: if IW[2]<>[] then for i from 1 while nops(IW1)<=x0 do for j from 1 to nops(IW[2]) do IW1:=[op(IW1),IW[2][j]]: od: od: fi: LOS1:=LOS[1]: if LOS[2]<>[] then for i from 1 while nops(LOS1)<=x0 do for j from 1 to nops(LOS[2]) do LOS1:=[op(LOS1),LOS[2][j]]: od: od: fi: x0:=min(x0,nops(LOS1)): for i from 1 to x0 do lu:={}: for j from 1 to i-1 do if LOS1[i-j]-j>=0 then lu:=lu union {LOS1[i-j]-j}: fi: od: if LOS1[i]<>mex(lu union IW1[i]) then RETURN(false,LOS1,IW1): fi: od: true: end: ########What's needed for ChompLosers###### ChompLosers:=proc(N) local gu,mu,i,j: gu:=[[[],[1]]]: for j from 1 to N do mu:=InstWin1F(gu[1],nops(gu)): for i from 2 to nops(gu) do mu:=Ikhud(mu,InstWin1F(gu[i],nops(gu)-i+1)): od: gu:=[op(gu),LosersF(mu)]: od: gu: end: #######end ChompLosers InstWin1F:=proc(LS,x) local LS1: if LS[1]=[] and LS[2]<>[] then LS1:=[[LS[2][1]],[op(2..nops(LS[2]),LS[2]),LS[2][1]]]: else LS1:=LS: fi: Ikhud(InstWin1aF(LS1[1],x),InstWin1bF(LS1[2],nops(LS1[1]),x)): end: InstWin1aF:=proc(Seq1,x) local b0,mu,i,K: if Seq1=[] then RETURN([[],[{}]]): fi: b0:=Seq1[1]: K:=max(b0-x,nops(Seq1)-1): for i from 0 to K do mu[i]:={}: od: for i from 0 to b0-x do mu[i]:=mu[i] union {b0-x-i}: od: for i from x to nops(Seq1)-1 do mu[i-x]:=mu[i-x] union {Seq1[i+1]}: od: mu:=[seq(mu[i],i=0..K)]: for i from 1 to nops(mu) while mu[i]<>{} do od: [[op(1..i-1,mu)],[{}]]: end: #InstWin1bF(Seq1,k1,x): If [c,k1+i+nops(Seq1)*L,Seq1[i+1]],i=0..nops(Seq)-1 #is a loser finds the sequence Seq2 and an integer #k1 such that [c+x,k2+i+nops(Seq2)*L,Seq2[i+1]], i=0..nops(Seq)-1 # is an instant winner InstWin1bF:=proc(Seq1,k1,x) local mu,gu,R,i,L,k2: R:=nops(Seq1): if R=0 then RETURN([[],[{}]]): fi: gu:={}: for i from 0 to R-1 do for L from 0 while k1+i+R*L-x<0 do od: mu[k1+i+R*L-x]:=Seq1[i+1]: gu:=gu union {k1+i+R*L-x} od: k2:=min(op(gu)): [[{}$k2],[seq({mu[k2+i]},i=0..R-1)]]: end: #Losers(IW): Given the Instant Winners in symbolic form #IW=[INI,[Period]], returns the losers in symbolic form #[INI,[Period]] LosersF:=proc(IW) local i1,T,gu,kha,j,i,mu: T:=max(seq(op(IW[1][i1]),i1=1..nops(IW[1])), seq(op(IW[2][i1]),i1=1..nops(IW[2])))+2: gu:=Expand1(IW,4*T+nops(IW[1])): mu:=[]: for i from 1 to nops(gu) do kha:=gu[i]: for j from 1 to min(T,i)-1 do if mu[i-j]-j>=0 then kha:=kha union {mu[i-j]-j}: fi: od: mu:=[op(mu),mex(kha)]: if mu[nops(mu)]=0 then RETURN([mu,[]]): fi: od: mu:=GuessPeriod(mu): if nops(mu[2])>=T then RETURN(FAIL): fi: mu: end: ######### #SpellOut(Tab,L): using the table Tab spells out all the #losing positions [c,a,b] (3^c2^a1^b) with c+a+b<=L SpellOut:=proc(Tab,L) local mu,a0,mu1,a,c,gu: if L>nops(Tab)-1 then print(`Table not big enough`): RETURN(FAIL): fi: gu:={}: for c from 0 to L do mu:=Tab[c+1]: mu1:=mu[1]: if mu[2]<>[] then for a from nops(mu[1])+1 to L do a0:=(a-nops(mu[1])-1) mod nops(mu[2]): mu1:=[op(mu1),mu[2][a0+1]]: od: fi: for a from 0 to nops(mu1)-1 do if c+a+mu1[a+1]<=L then gu:=gu union {[c,a,mu1[a+1]]}: fi: od: od: gu: end: #AllMoves(POS): All moves from position [c,a,b] (i.e. 3^c2^a1^b) #(i.e. (c+a+b,c+a,a)). For example, try AllMoves([1,1,1]); AllMoves:=proc(POS) local gu,a,b,c,x: if POS=[0,0,1] then RETURN({}): fi: gu:={}: c:=POS[1]: a:=POS[2]: b:=POS[3]: for x from 1 to c do gu:=gu union {[c-x,x+a,b],[c-x,0,a+b+x],[c-x,0,0]}: od; for x from 1 to a do gu:=gu union {[c,a-x,b+x],[c,a-x,0]}: od; for x from 1 to b do gu:=gu union {[c,a,b-x]}: od; gu: end: WinningMoves:=proc(POS,Tab): AllMoves(POS) intersect SpellOut(Tab,convert(POS,`+`)): end: #GrundyDirect(L): The table of the Grundy function of all #[c,a,b] with c+a+b<=L GrundyDirect:=proc(L) local T,POS,a,b,c,i,gu,lu,S1,hakhi: lu:={}: for c from 0 to L do for a from 0 to L-c do for b from 0 to L-c-a do POS:=[c,a,b]: if POS<>[0,0,0] then lu:=lu union {POS}: gu:=AllMoves(POS): T[POS]:=mex({seq(T[gu[i]],i=1..nops(gu))}): fi: od: od: od: hakhi:=max(seq(T[lu[i]],i=1..nops(lu))): op(T),hakhi: for i from 0 to hakhi do S1[i]:={}: od: for i from 1 to nops(lu) do S1[T[lu[i]]]:=S1[T[lu[i]]] union {lu[i]}: od: [seq(S1[i],i=0..hakhi)]: end: SetToSeq1:=proc(Set1) local gu,i,T,lu,gu1: lu:=sort([seq(Set1[i][1],i=1..nops(Set1))]): for i from 1 to nops(lu) do T[lu[i]]:={}: od: for i from 1 to nops(Set1) do T[Set1[i][1]]:=T[Set1[i][1]] union {Set1[i][2]}: od: gu:=[]: gu1:=[]: for i from 1 to nops(lu) do if nops(T[lu[i]])<>1 then RETURN(FAIL): else gu1:=[op(gu1),lu[i]]: gu:=[op(gu),T[lu[i]][1]]: fi: od: if gu1<>[seq(i,i=0..nops(gu1)-1)] then RETURN(FAIL): fi: gu: end: SetToSeqOld:=proc(Set1) local gu,i,T,lu,gu1,lu1: lu:=sort(convert({seq(Set1[i][1],i=1..nops(Set1))},list)): for i from 1 to nops(lu) do T[lu[i]]:={}: od: for i from 1 to nops(Set1) do T[Set1[i][1]]:=T[Set1[i][1]] union {[Set1[i][2],Set1[i][3]]}: od: gu:=[]: gu1:=[]: for i from 1 to nops(lu) do gu1:=[op(gu1),lu[i]]: lu1:=SetToSeq1(T[lu[i]]): if lu1[nops(lu1)]=0 then gu:=[op(gu),[lu1,[]]]: else gu:=[op(gu),GuessPeriod(lu1)]: fi: od: if gu1<>[seq(i,i=0..nops(gu1)-1)] then RETURN(FAIL): fi: gu: end: SetToSeq:=proc(Set1) local gu,i,T,lu,gu1,lu1: lu:=sort(convert({seq(Set1[i][1],i=1..nops(Set1))},list)): for i from 1 to nops(lu) do T[lu[i]]:={}: od: for i from 1 to nops(Set1) do T[Set1[i][1]]:=T[Set1[i][1]] union {[Set1[i][2],Set1[i][3]]}: od: gu:=[]: gu1:=[]: for i from 1 to nops(lu) do gu1:=[op(gu1),lu[i]]: lu1:=SetToSeq1(T[lu[i]]): if lu1[nops(lu1)]=0 then gu:=[op(gu),[lu1,[]]]: else lu1:=GuessPeriod(lu1): if lu1=FAIL then RETURN(gu): else gu:=[op(gu),lu1]: fi: fi: od: if gu1<>[seq(i,i=0..nops(gu1)-1)] then RETURN(FAIL): fi: gu: end: #GrundyDirectNice(L): The table of the Grundy function of all #[c,a,b] with c+a+b<=L, in Ultimately Periodic Notation #(as far as possible with the data) GrundyDirectNice:=proc(L) local i,gu: gu:=GrundyDirect(L): [seq(SetToSeq(gu[i]),i=1..nops(gu))]:end: Xinyu:=proc(U) local U1,U2,i: U1:=U[1]: U2:=U[2]: U1:=[seq({U1[i]},i=1..nops(U1))]: if U2=[] then U2:=[{}]: else U2:=[seq({U2[i]},i=1..nops(U2))]: fi: [U1,U2]: end: #ChompGrundy(N,G): Given positive integers N and G, #outputs a list of lists Resh such that Resh[g+1][c+1] describes #the Chomp positions 1^b2^a3^c (i.e. top row having a+b+c cells, #middle row b+c, and bottom row c cells) with whose Spargue-Grundy #value equals g, given in ultimately-periodic notation [INI,Period] #such that the resulting sequence [op(INI),op(Period),op(Period), ...] # is such that the (a+1)^th entry equals b. #For example try: ChompGrundy(10,3); ChompGrundy:=proc(N,G) local gu,mu,j,muK,IW,LOS,g,YASHAN,GU,i1: YASHAN:=[[[{0}],[{}]],[[],[{}]]$N]: GU:=[]: for g from 0 to G do LOS:=Losers(YASHAN[1]): gu:=[LOS]: if LOS=[[0],[]] then GU:=[op(GU),gu]: YASHAN:=[seq(Ikhud(YASHAN[i1],Xinyu(gu[i1])),i1=1..nops(gu)), seq(YASHAN[i1],i1=nops(gu)+1..N+1)]: break: fi: mu:=InstWin1(gu[1],nops(gu)): for j from 1 to N do IW:=Ikhud(mu): IW:=Ikhud(IW,YASHAN[j+1]): LOS:=Losers(IW): if LOS=[[0],[]] then gu:=[op(gu),LOS]: YASHAN:=[seq(Ikhud(YASHAN[i1],Xinyu(gu[i1])),i1=1..nops(gu)), seq(YASHAN[i1],i1=nops(gu)+1..N+1)]: break: fi: gu:=[op(gu),LOS]: if not ProveLosers(LOS,IW) then RETURN([op(GU),gu]): fi: muK:=InstWin1(gu[nops(gu)],1): mu:=Ikhud(OneLess(mu[1]),muK[1]),Ikhud(ShiftLeft(mu[2]),muK[2]): od: GU:=[op(GU),gu]: YASHAN:=[seq(Ikhud(YASHAN[i1],Xinyu(gu[i1])),i1=1..nops(gu)), seq(YASHAN[i1],i1=nops(gu)+1..N+1)]: od: GU: end: #CheckChompGrundy(N,G,L): Checks the validity of procdeure #ChompGrundy by comparing it to the raw data generated by #GrundyDirect up to L cells. For example, try #CheckChompGrundy(10,3,20) CheckChompGrundy:=proc(N,G,L) local gu,lu,i: gu:=ChompGrundy(N,G): lu:=GrundyDirectNice(L): {seq( evalb ([op(1..min(nops(gu[i]),nops(lu[i])),gu[i])]= [op(1..min(nops(gu[i]),nops(lu[i])),lu[i])] ), i=1..G+1)}: end: #Larson(): (Added June 5, 2015, inspired by Craig Larson's conjecture), #outputs the sequence of the minimum of alpha-gamma amongs all Winning (P) positions with three rows where #[alpha,beta,gamma] denotes the position (alpha+beta+gamma,alpha+beta,alpha) in the usual notation #for alpha from 0 to 400 #According to Craig Larson's conjecture, it is >=-1, but has alpha gets bigger it seems to get bigger. #Try: Larson(); Larson:=proc() local lu,i,lu1,lu1a,lu1b,gu,j: lu:=ChompLosers400: gu:=[]: for i from 0 to 400 do lu1:=lu[i+1]: lu1a:=lu1[1]: lu1b:=lu1[2]: lu1:=[op(lu1a),op(lu1b)]: gu:=[op(gu),min(seq(i-lu1[j],j=1..nops(lu1))) ]: od: gu: end: