Udz:=[2,1,0,2,0,1,2,0,2,1,2,0,1,0,2,0,1,2]:
Vdz:=[2,1,0,2,0,1,0,2,1,2,0,2,1,0,2,0,1,2]:
 
print(` Version of Aug. 26, 1998`):
print(`This is JAN, A Maple package`):
print(`that  studies (so far) Square-Free words`):
print(` Named in honor of JAN BRINKUIS, and inspired in part by`):
print(` his brilliant paper: "Non-Repetitive Sequences on three symbols"`):
print(` Quart. J. Math.  Oxford (2), 34 (1983), 145-149 `):
lprint(``):
print(`Written by Doron Zeilberger.`):
lprint(``):
print(`The currrent version is available from`):
print(` http://www.math.temple.edu/~zeilberg`):
lprint(``):
print(`For general help, and a list of the available functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name)" `):
lprint(``):
print(`Please report all bugs to zeilberg@math.temple.edu `):
 
 
 
ezra:=proc()
if args=NULL then
 
print(`This is JAN, A Maple package`):
print(`that  studies (so far) Square-Free words`):
print(` Named in honor of JAN BRINKUIS, and inspired in part by`):
print(` his brilliant paper: "Non-Repetitive Sequences on three symbols" `):
print(` Quart. J. Math.  Oxford (2), 34 (1983), 145-149 `):
lprint(``):
print(`Written by Doron Zeilberger.`):
lprint(``):
print(` Contains Procedures `):
print(`Aristo, CheckJan, FindPair,isSqFr, GoodUV, Images1, JB`):
print(`Metsa, Mipui, PLU1, Prefixes, Sqfree, Suffixes, T `):
print(` For specific help type "ezra(procedure_name); " `):
fi:
 
if nops([args])=1 and op(1,[args])=`CheckJan` then
print(`CheckJan(WordSet); Given a set of words, WordSet,`):
print(`all of length 2k, say, checkes whether for`):
print(`each length r, the set of heads and tails of`):
print(`length r, k<=r<2k, are all distinct`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Prefixes` then
print(`Prefixes(WordSet,k): Given a set of words WordSet,`):
print(`finds its prefixes of first k letters`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Suffixes` then
print(`Suffixes(WordSet,k): Given a set of words WordSet,`):
print(`finds its suffixes of last k letters`):
fi:
 
if nops([args])=1 and op(1,[args])=`T` then
print(`T(): The set T of  Image  words`):
fi:
 
if nops([args])=1 and op(1,[args])=`JB` then
print(`JB(K): Finds the shortest possible Brinkhuis pair`):
print(`and checks its validity up to images of length K`):
fi:
 
if nops([args])=1 and op(1,[args])=`FindPair` then
print(`FindPair(): finds the smallest Brinkhuis pair`):
fi:
 
if nops([args])=1 and op(1,[args])=`isSqFr` then
print(`isSqFr(w) : returns true if the words w is square-free`):
fi:
 
if nops([args])=1 and op(1,[args])=`Images1` then
print(`Images1(U,V,k): all the images, according to the`):
print(`pair of words U,V, of square-free words of length`):
print(`k, under all possible 0-1 vectors of length k`):
print(`it also checks whether they are all square-free`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Mipui` then
print(`Mipui(U,V,w,Bin1): Given two words U,V, and a word`):
print(`w, and a binary words (in 0,1) Bin1 finds the`):
print(`longer word obtained by replacing 0 by U[V], 1`):
print(`by U1[V1] and 2 by U2[V2] the word Bin1 is the guide`):
print(`to whether replace it by U or V`):
fi:
 
if nops([args])=1 and op(1,[args])=`Metsa` then
print(`Metsa(n): Finds a pair of good words U , V`):
print(`or returns 0`):
fi:
 
if nops([args])=1 and op(1,[args])=`GoodUV` then
print(`GoodUV(U,V): checkes whether (U+1)V (U+2)V`):
print(`V(U+1) and V(U+2) are all square-free`):
print(`the first-halves of the set T:={U,U+1,U+2,V,V+1,V+2}`):
print(`are all distinct and ditto for second-halves`):
fi:
 
if nops([args])=1 and op(1,[args])=`Aristo` then
print(`Aristo(n): the set of square-free words w of length n`):
print(`on the alphabet {0,1,2}, that have the property`):
print(`that w,w+1, w,w+2, w+1,w, w+2,2 are all square-free`):
fi:
 
if nops([args])=1 and op(1,[args])=`PLU1` then
print(`PLU1(w): Given a word w in {0,1,2} finds the`):
print(`sequence obtained by adding 1 mod 3`):
fi:
 
if nops([args])=1 and op(1,[args])=`Sqfree` then
print(`Sqfree(alphabet,LENGTH): Given a set of letters alphabet, and`):
print(`a non-negative integer LENGTH finds the set of square-free`):
print(`words of lentgh LENGTH in the alphabet`):
fi:
 
end:
 
 
#isbad(w) : returns true if the words w ends with
#a square
isbad:=proc(w) 
local i:
for i from 1 to trunc(nops(w)/2) do
if op(nops(w)-2*i+1..nops(w)-i,w)=op(nops(w)-i+1..nops(w),w) then
RETURN(true):
fi:
od:
false:
end:
 
 
#isSqFr(w) : returns true if the words w is square-free
isSqFr:=proc(w) 
local i,j,w1:
 
for i from 1 to nops(w) do
 for j from i+1  to nops(w) do
   w1:=[op(i..j,w)]:
 if  nops(w1) mod 2 =0 and op(1..nops(w1)/2,w1)=op(nops(w1)/2+1..nops(w1),w1) 
then
  RETURN(false):
 fi:
od:
od:
true:
end:
 
 
#Kadima(w,OPTS,opts): Given a word w, and the corresponding
#lists of options open, adds one letter, from the set opts
 
Kadima:=proc(w,OPTS,opts)
local i,j,opts1:
opts1:=opts:
 
for i from 1 to nops(opts) do
 
if not isbad([op(w),op(i,opts)]) then
 RETURN([op(w),op(i,opts)],[op(OPTS),opts1 minus {op(i,opts)}]):
else
opts1:=opts1 minus {op(i,opts)}:
fi:
 
od:
 
for j from 1 while OPTS[nops(OPTS)-j]={} do
od:
print(j):
[op(1..nops(w)-j-1,w)],[op(1..nops(OPTS)-j-2,OPTS), 
op(nops(OPTS)-j-1,OPTS) minus {op(nops(w)-j-1,w)}]:
end:
 
Rand1:=proc(n)
local i,w,ra,opt1:
w:=[1]:
ra:=rand(1..2):
 
for i from 1 to n do
 opt1:={1,2,3} minus {op(nops(w),w)}:
w:=[op(w),op(ra(),opt1)];
 
if isbad(w) then
RETURN(0):
fi:
 
od:
w:
end:
 
Rand2:=proc(n,K)
local i,w:
 
for i from 1 to K do
w:=Rand1(n):
if w<>0 then
RETURN(w):
fi:
od:
0:
end:
 
 
#Sqfree(alphabet,LENGTH): Given a set of letters alphabet, and
#a non-negative integer LENGTH finds the set of square-free
#words of lentgh LENGTH in the alphabet
 
Sqfree:=proc(alphabet,LENGTH)
local w,i,se,se1,ot1,j,w1:
option remember:
 
if not type(alphabet,set) or not type(LENGTH, integer) or LENGTH<0 then
 ERROR(`Bad input`):
fi:
 
if LENGTH=0 then
 RETURN({[]}):
fi:
 
se1:=Sqfree(alphabet,LENGTH-1):
 
se:={}:
for i from 1 to nops(se1) do
w:=op(i,se1):
 
for j from 1 to nops(alphabet) do
ot1:=op(j,alphabet):
w1:=[op(w),ot1]:
 
if member([op(2..nops(w1),w1)],se1) then
 if not (nops(w1) mod 2 =0 and op(1..nops(w1)/2,w1)=
op(nops(w1)/2+1..nops(w1),w1)) 
then
 se:=se union {[op(w),ot1]}:
fi:
fi:
od:
od:
se:
end:
 
 
#GoodGood(u,v): If square-free word u is placed in front 
#square-free word v whether the concatanation uv
#is square-free
GoodGood:=proc(u,v)
local i,j,w1:
for i from 1 to nops(u) do
for j from 1 to nops(v)  do
w1:=[op(i..nops(u),u),op(1..j,v)]:
 
 if nops(w1) mod 2 =0 and op(1..nops(w1)/2,w1)=
op(nops(w1)/2+1..nops(w1),w1) then
RETURN(false):
fi:
od:
od:
true:
end:
 
 
#PLU1(w): Given a word w in {0,1,2} finds the
#sequence obtained by adding 1 mod 3
PLU1:=proc(w)
local i:
[seq(w[i]+1 mod 3, i=1..nops(w))]:
end:
 
 
#Aristo(n): the set of square-free words w of length n
#on the alphabet {0,1,2}, that have the property
#that w,w+1, w,w+2, w+1,w, w+2,2 are all square-free
 
Aristo:=proc(n)
local gu,lu,i,w,w1,w2:
option remember:
gu:=Sqfree({0,1,2},n):
lu:={}:
 
for i from 1 to nops(gu) do
w:=op(i,gu):
w1:=PLU1(w):
w2:=PLU1(w1):
 
if (
GoodGood(w,w1) and GoodGood(w,w2) and
GoodGood(w1,w) and GoodGood(w2,w) ) then
lu:=lu union {w}:
fi:
od:
 
lu:
 
end:
 
 
#CheckJan(WordSet); Given a set of words, WordSet,
#all of length 2k, say, checkes whether for
#each length k<=r<2k, the set of heads and tails of
#length r are all distinct
 
CheckJan:=proc(WordSet)
local gu,i,k,r:
 
if nops({seq(nops(op(i,WordSet)),i=1..nops(WordSet))})<>1 then
ERROR(`The set of words must all be of the same length`):
fi:
 
k:=nops(op(1,WordSet)):
 
for r from  trunc((k+1)/2) to k-1 do
if nops(Suffixes(WordSet,r) union Prefixes(WordSet,r))<> 2*nops(WordSet) then
RETURN(false):
fi:
od:
 
true:
 
end:
 
 
#GoodUV(U,V): checkes whether (U+1)V (U+2)V
#V(U+1) and V(U+2) are all square-free and the
#the first-halves of the set T:={U,U+1,U+2,V,V+1,V+2}
#are all distinct and ditto for second-halves
GoodUV:=proc(U,V)
local V1,V2,U1,U2,T1:
V1:=PLU1(V):V2:=PLU1(V1):U1:=PLU1(U):U2:=PLU1(U1): 
T1:={U,V,U1,V1,U2,V2}:
 
if GoodGood(U,V1) and GoodGood(U,V2) and GoodGood(V1,U) and GoodGood(V2,U)  
and CheckJan(T1) then
true:
else
false:
fi:
 
end:
 
#Metsa(n): Finds a pair of good words U , V
#or returns 0
Metsa:=proc(n)
local U,V,gu,i,j:
gu:=Aristo(n):
 
for i from 1 to nops(gu) do
U:=op(i,gu):
 
for j from i+1 to nops(gu) do
V:=op(j,gu):
 
if GoodUV(U,V) then
RETURN(U,V):
fi:
od:
 
od:
0:
end:
 
 
#Mipui(U,V,w,Bin1): Given two words U,V, and a word
#w, and a binary words (in 0,1) Bin1 finds the
#longer word obtained by replacing 0 by U[V], 1
#by U1[V1] and 2 by U2[V2] the word Bin1 is the guide
#to whether replace it by U or V
Mipui:=proc(U,V,w,Bin1)
local i,W,ot1,bit1,U1,U2,V1,V2:
U1:=PLU1(U):
U2:=PLU1(U1):
 
V1:=PLU1(V):
V2:=PLU1(V1):
 
W:=[]:
 
for i from 1 to nops(w) do
ot1:=op(i,w):
bit1:=op(i,Bin1):
 
if bit1=0 then
if ot1=0 then
W:=[op(W),op(U)]:
 
elif ot1=1 then
W:=[op(W),op(U1)]:
 
elif ot1=2 then
W:=[op(W),op(U2)]:
fi:
 
elif bit1=1 then
 
if ot1=0 then
W:=[op(W),op(V)]:
 
elif ot1=1 then
W:=[op(W),op(V1)]:
 
elif ot1=2 then
W:=[op(W),op(V2)]:
fi:
 
fi:
od:
 
W:
end:
 
#UCube(n):Unit cube of dimension n
UCube:=proc(n)
local i,gu,mu,w:
 
if n=0 then
 RETURN({[]}):
fi:
 
mu:=UCube(n-1):
gu:={}:
for i from 1 to nops(mu) do
w:=op(i,mu):
gu:=gu union {[op(w),0],[op(w),1]}:
od:
 
gu:
end:
 
 
#Images1(U,V,k): all the images, according to the
#pair of words U,V, of square-free words of length
#k, under all possible 0-1 vectors of length k
#it also checks whether they are all square-free
 
Images1:=proc(U,V,k)
local mu,gu,lu,i,j,w,Bin1,anne1:
 
gu:={}:
 
mu:=Sqfree({0,1,2},k):
lu:=UCube(k):
 
for i from 1 to nops(mu) do
 w:=op(i,mu): 
 for j from 1 to nops(lu) do
  Bin1:=op(j,lu):
 anne1:=Mipui(U,V,w,Bin1):
  if not isSqFr(anne1) then
    print(`bad news!, with`):
    print(`the original square-free word`,w):
    print(`and the binary word`, Bin1):
    print(`the image,`, anne1, `is not square-free`):
    RETURN(anne1):
  fi:
    gu:=gu union {anne1}:
 od:
od:
 
print(`Good news!, they are all square-free!`):
gu:
 
end:
 
 
#FindPair(): finds the smalles Brinkhuis pair
FindPair:=proc()
local i,gu:
 
for i from 1 do
gu:=Metsa(i):
if gu<>0 then
RETURN(gu):
fi:
od:
end:
 
 
#JB(K): Finds the shortest possible Brinkhuis pair
#and checks its validity up to images of length K
JB:=proc(K)
local k,gu,U,V:
gu:=FindPair():
U:=gu[1]: V:=gu[2]:
print(`The shortest Brunkhuis pair is`):
print(U,V):
 
 
for k from 1 to K do
Images1(U,V,k):
od:
 
U,V:
 
end:
 
 
 
#T(): The set T of  Image  words
T:=proc()
local U,V:
U:=[2,1,0,2,0,1,2,0,2,1,2,0,1,0,2,0,1,2]:
V:=[2,1,0,2,0,1,0,2,1,2,0,2,1,0,2,0,1,2]:
{U,V,PLU1(U),PLU1(PLU1(U)),PLU1(V),PLU1(PLU1(V))}:
end:
 
#Prefixes(WordSet,k): Given a set of words WordSet,
#finds its prefixes of first k letters
Prefixes:=proc(WordSet,k)
local gu,i,w:
gu:={}:
for i from 1 to nops(WordSet) do
w:=op(i,WordSet):
 
if nops(w)>=k then
gu:=gu union {[op(1..k,w)]}:
fi:
 
od:
 
gu:
 
end:
 
 
#Suffixes(WordSet,k): Given a set of words WordSet,
#finds its suffixes of last k letters
Suffixes:=proc(WordSet,k)
local gu,i,w:
gu:={}:
for i from 1 to nops(WordSet) do
w:=op(i,WordSet):
 
if nops(w)>=k then
gu:=gu union {[op(nops(w)-k+1..nops(w),w)]}:
fi:
 
od:
 
gu:
 
end: