Some examples of Walnut
Jeffrey Shallit

You can just cut and paste these examples directly into the window
running the program.

--

1.  For which n does the Thue-Morse word have a square xx where
|x| = n ?

eval tmsquarelengths "Ej Ai (i<n) => T[j+i] = T[j+n+i]":

--

2.  For which n does the Thue-Morse word have a palindrome of
length n?

eval paltm "Ei Aj (j<n) => T[i+j] = T[(i+n)-(j+1)]":

--

3.  For which n does the Thue-Morse word have an overlap axaxa where
|ax| = n?

eval tmoverlaplengths "Ej Ai (i<=n) => T[j+i] = T[j+n+i]":

--

4.  For which n does the Fibonacci word have a cube xxx where |x| = n?

eval fibcubes "?msd_fib Ei Ak (k<2*n) => F[i+k]=F[i+n+k]":

--

5.  Is the Thue-Morse sequence ultimately periodic, yes or no?

eval tmup "En Ei n>=1 & Aj (j>=i) => T[j] = T[n+j]":

--

6.  Is the Thue-Morse sequence mirror invariant, yes or no?
("Mirror invariant" means if a block appears, so does its reverse.)

eval thuemirror "An Ai Ej At (t<n) => T[i+t] = T[(j+n)-(t+1)]":

--

7.  Is the Thue-Morse sequence recurrent, yes or no?
("Recurrent" means that every block that appears, appears infinitely
often.  This is the same as saying that every block that appears,
appears at least twice.)

eval tmrecur "Ai,n Ek (k>i) & At (t<n) => T[i+t] = T[k+t]":

--

8.  Is the Thue-Morse sequence uniformly recurrent, yes or no?
("Uniformly recurrent" means there is a constant c(n) such that
every block of length n that appears, appears again at a distance
at most c(n) positions from the previous occurrence.)

eval tmur "An El Ai Es s>i & s<=i+l & Aj (j<n) => T[i+j]=T[s+j]":

--

9.  For which n does the Thue-Morse word have an unbordered factor
of length n?
(A factor is "bordered" if it begins and ends with the same word,
in a nontrivial way.  It is unbordered otherwise.)

eval tmunb "Ei Aj (j>=1 & 2*j<=n) => Et (t<j) & T[i+t]!=T[(i+n+t)-j]":

--

10.  For which n does the Thue-Morse word have a rich word of length n?
Here we use the characterization that a word is rich if the longest
palindromic suffix of every prefix p occurs exactly once in p.

eval richtm "El As Ar ((l<=r)&(r<=s)&(s<l+n)) => (( (Ai (i+r<=s) => T[r+i]=T[s-i]) & (Au ((l<=u)&(u<r)) => (Ej (j+u<=s) & T[u+j] != T[s-j]))) => (Ah ((l<=h)&(h<r)) => (Ek (k+r<=s) & T[h+k] != T[r+k])))":

--

11.  For which p is the Fibonacci word quasiperiodic of period p?

def fibquasi "?msd_fib Ai Ej i<j+n & j<=i & Ak (k<n) => F[k]=F[k+j]":

--

12.  For which n are there anti-palindromes x x' with |x| = n in Thue-Morse?

eval tmantipal "Ei Aj (j<n) => T[i+j]!=T[i+j+n]":

--

13.  For which n is there a factor of length n occurring
both in Thue-Morse AND Rudin-Shapiro?

eval tmrs "Ei,j Ak (k<n) => T[i+k] = RS[j+k]":

--

14.  For which n is there a factor of the form x x x^R in Thue-Morse,
with |x| = n?

eval tmxxxr "Ei At (t<n) => (T[i+t]=T[i+t+n] & T[i+t]=T[(i+3*n)-(t+1)])":

--

15.  For which n is there a factor of the form x x x^R in the Rote-Fibonacci
word with |x| = n?

You'd like to write

eval rote1 "?msd_fib Ei At ((t<n) => ((R[i+t]=R[i+t+n]) & (R[i+t]=R[(i+3*n)-(t+1)])))":

as in the previous example, but this runs out of space.  So instead 
write

eval rote2 "?msd_fib Ei (At (t<n) =>(R[i+t]=R[i+t+n])) & (At (t<n) => (R[i+2*n+t] = R[(i+2*n)-(t+1)]))":

Even faster is

eval rote3 "?msd_fib Ei Ej (j=i+2*n) & (At (t<n) =>(R[i+t]=R[i+t+n])) & (At (t<n) => (R[j+t]=R[j-(t+1)]))":

which illustrates the idea of introducing auxiliary variables to decrease
state blow-up.

16.  For which n is there a privileged factor of length n in the Thue-Morse
word?  Here we use a criterion of Luke Schaeffer, which says that a word
w is privileged if for all m, 1 <= m <= |w|, there exists a word x
with 1 <= |x| <= m such that x occurs as both a prefix and suffix of w
and there are no other occurrences of x in the first m symbols of w,
nor in the last m symbols of w.

eval tmpriv "Ei Am ((m >= 1)&(m <= n))  => Et (t >= 1)&(t <= m)& (As (s <t) => T[i+s]=T[(i+n+s)-t]) & (Aj ((j >= 1)&(j <= m-t)) => ((Ek (k<t) & T[i+k] != T[i+j+k]) & (El (l<t) & T[(i+l+n)-t] != T[(i+n+j+l)-(m+1)])))":

This can also be done using the "def" command, as follows:

def thuefactoreq "Ak (k < n) => T[i+k] = T[j+k]":
def thueuniquepref "Aj (j > 0 & j+m < n) => ~$thuefactoreq(i,i+j,m)":
def thueuniquesuff "Aj (j > 0 & j+m < n) => ~$thuefactoreq((i+n)-m,(i+n)-(m+j),m)":
def thuepriv "(n >= 1) & Am (m <= n & m >= 1) => (Ep (p <= m & p >= 1) & $thueuniquepref(i,p,m) & $thueuniquesuff((i+n)-m,p,m) & $thuefactoreq(i, (i+n)-p, p))":
eval thuepriv2 "Ei $thuepriv(i,n)":

(Solution by Luke Schaeffer)