# Experimental Math - Homework 22 - Due Sunday, April 15 # Phil Benjamin # Note: this file may be freely posted on the Experimental Math Website ############################################################## # SplitUp(L) # Input: List L interpreted as a word in alphabet {1,2,3} # Output: List of lists where each element is "atomic" SplitUp := proc(L) # Strategy: find two "cut points" in L: # L = L1,L2,Letc with split(L1,L2) --> true # then apply SplitUp to Letc local L1, L2, Letc, i1, i2; if nops(L) = 0 then return []; end if; if nops(L) = 1 then return [L]; end if; if nops(L) = 2 then if split([L[1]],[L[2]]) then return [[L[1]],[L[2]]]; end if; return [L]; end if; # i1, i2 are Last indices for L1 and L2 for i1 from 1 to nops(L) - 1 do for i2 from i1 + 1 to nops(L) do if split(L[1..i1],L[(i1+1)..i2]) then return [L[1..i1],L[(i1+1)..i2],op(SplitUp(L[(i2+1)..nops(L)]))]; end if; end; end; return [L]; end: SplitUp2 := proc(L) # Strategy: find a "cut point" in L: # L = L1,Letc with split(L1,Letc) --> true # then apply SplitUp to Letc local L1, Letc, i; if nops(L) = 0 then return []; end if; if nops(L) = 1 then return [L]; end if; # i is Last index for L1 for i from 1 to nops(L) - 1 do if split(L[1..i],L[(i+1)..nops(L)]) then return [L[1..i],op(SplitUp2(L[(i+1)..nops(L)]))]; end if; end; return [L]; end: # Apply JC transform n times to L JCn := proc(w,n) local w1, i; if n = 0 then return w; end if; w1 := w; for i from 1 to n do w1 := JC(w1); end; return w1; end: ############################################################## # JC(w) # Input word as a list # "Look and Say" transform of the list #The Conway Look-And-Say sequence #JC(w): inputs any list in and outputs its #Yusra transform #a1^c1,a2^c2,..., ar^cr ->[a1,c1,a2,c2,a3,c3, ...] JC:=proc(w) local i,a1,c1,w1,J1: option remember: if w=[] then RETURN([]): fi: a1:=w[1]: for i from 1 to nops(w) while w[i]=a1 do od: c1:=i-1: w1:=w[c1+1..nops(w)]: J1:=JC(w1): [c1,a1,op(J1)]: end: ############################################################## # split utility from ~zeilberg/EM12/split.txt split:=proc(L,R) local n,m: if nops(L)=0 or nops(R)=0 then RETURN(1): fi: n:=op(nops(L),L): m:=op(1,R): if n=m then RETURN(false): fi: if n>=4 and m<=3 then RETURN(true): fi: if n=2 then if m=1 and nops(R)>2 and op(2,R)<>1 and op(3,R)<>op(2,R) then RETURN(true): fi: if m=1 and nops(R)=2 and op(2,R)<>1 then RETURN(true): fi: if m=1 and nops(R)>=3 and op(2,R)=1 and op(3,R)=1 then RETURN(true): fi: if m=3 and nops(R)>=2 and op(2,R)<>3 and not(nops(R)>=4 and op(2,R)=op(3,R) and op(3,R)=op(4,R)) then RETURN(true): fi: if m=3 and nops(R)=1 then RETURN(true): fi: if m>=4 then RETURN(true): fi: fi: if n<>2 then if nops(R)>=5 and op(1,R)=2 and op(2,R)=2 and op(3,R)=1 and op(4,R)<>1 and op(5,R)<>op(4,R) then RETURN(true): fi: if nops(R)=4 and op(1,R)=2 and op(2,R)=2 and op(3,R)=1 and op(4,R)<>1 then RETURN(true): fi: if nops(R)>=5 and op(1,R)=2 and op(2,R)=2 and op(3,R)=1 and op(4,R)=1 and op(5,R)=1 then RETURN(true): fi: if nops(true)>=4 and op(1,R)=2 and op(2,R)=2 and op(3,R)=3 and op(4,R)<>op(3,R) and not(nops(R)>=6 and op(4,R)=op(5,R) and op(5,R)=op(6,R)) then RETURN(true): fi: if nops(R)=2 and op(1,R)=2 and op(2,R)=2 then RETURN(true): fi: if nops(R)=3 and op(1,R)=2 and op(2,R)=2 and op(3,R)>=4 then RETURN(true): fi: if nops(R)>=3 and op(1,R)=2 and op(2,R)=2 and op(3,R)>=4 and op(4,R)<>op(3,R) then RETURN(true): fi: fi: false: end: