An ‘Experimental Mathematics’ Approach to Stolarsky Interspersions via Automata Theory Jeffrey Shallit Abstract We look at the Stolarsky interspersions (such as the Wythoff array) one more time, this time using tools from automata theory. These tools allow easy verification of many of the published results on these arrays, as well as proofs of new results. 1 Introduction Let the Fibonacci numbers be denoted, as usual, by F_{1}=1,\ F_{2}=1,\ \text{and $F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 3$}. We can generalize this sequence by allowing two arbitrary starting values, to get the generalized Fibonacci numbers: F^{a,b}_{1}=a,\ F^{a,b}_{2}=b,\ \text{ and $F^{a,b}_{n}=F^{a,b}_{n-1}+F^{a,b}_{n-2}$ for $n\geq 3$.} (1) These sequences have been studied for at least 120 years [ 23 ] and probably longer. As Tagiuri observed, a simple induction gives a useful formula for the n ’th term of a generalized Fibonacci sequence in terms of the ordinary Fibonacci sequence. F^{a,b}(n)=aF_{n-2}+bF_{n-1} (2) for n\geq 3 . Several authors have studied Stolarsky interspersions , which are two-dimensional arrays {\bf A}=(A_{i,j})_{i,j\geq 1} of positive integers, strictly increasing across rows and down columns. The first row consists of the Fibonacci numbers (F_{n})_{n\geq 1} , and each succeeding row is a generalized Fibonacci sequence. The term A_{i,1} in the first column is defined to be the smallest positive integer that appeared in no preceding row. More formally, for a set S\subsetneq\mathbb{N} , we define the \mex function ( m inimal ex cluded element) \mex(S)=\min\{x\,:\,x\not\in S\}; then A_{i,1}:=\mex(\{A_{i^{\prime},j}\,:\,1\leq i^{\prime} ; logical IFF is written <=> . The command def defines an automaton for later use, while eval evaluates a first-order expression with no free variables and returns TRUE or FALSE . The command reg allows the user to specify an automaton through a regular expression. (For more about regular expressions, see [ 6 ] .) For example, here is the Walnut command that computes the automaton in Figure 1 . def odd "?msd_fib Ek n=2*k+1": For the automaton in Figure 2 , we use the command def double1 "?msd_fib z=2*n+1": Notice that this expression z=2*n+1 has two free variables, z and n , so the produced automaton has transitions on pairs of letters. The order of inputs is alphabetical order on the variable names when the command is defined; in this example, n is spelled out by the first coordinates of inputs and z is spelled out by the second coordinates. Lemma 1 . Suppose (a)_{F}=x and (b)_{F}=x0 . Then (a+b)_{F}=x00 . Proof. We first build a ‘shift’ automaton that accepts inputs x and y iff y=x0 . We can do this in Walnut with a regular expression: reg shift msd_fib msd_fib "([0,0]|[0,1][1,1]*[1,0])*": This produces the two-state automaton in Figure 3 . Figure 3: Automaton for the shift. Now we verify that if y=x0 and z=y0 then z=x+y . eval lem4 "?msd_fib Ax,y,z ($shift(x,y) & $shift(y,z)) => z=x+y": And Walnut returns TRUE . The theorem is proved. ∎ Lemma 2 . Let a,b be integers with a\geq 0 and b=\lfloor\alpha a\rfloor+\epsilon for \epsilon\in\{0,1\} . Define the generalized Fibonacci sequence F^{a,b} by ( 1 ). Then (F^{a,b}(n))_{F}=(F^{a,b}(3))_{F}\,0^{n-3} (4) for n\geq 3 . Proof. It suffices to show that (F^{a,b}(4))_{F}=(F^{a,b}(3))_{F}\,0 , because then ( 4 ) follows by induction from Lemma 1 . We define b=\lfloor\alpha a\rfloor+\epsilon , c=a+b , and d=b+c . Then we need to show that (d)_{F}=(c)_{F}\,0 . eval fab "?msd_fib Aa,b,c,d,x ($phin(a,x) & (b=x|b=x+1) & c=a+b & d=b+c) => $shift(c,d)": And Walnut returns TRUE . Here phin is an automaton of two inputs n and x that accepts if and only if x=\lfloor\alpha n\rfloor . It can be found, for example, in [ 19 , p. 278] . ∎ It would be very nice if there were automata taking three inputs i,j,x in parallel for which A_{i,j}=x for the arrays \bf A we discuss here. (Indeed, this nice property is true for the arrays in [ 20 ] .) Unfortunately, for the arrays we discuss in this paper, this is not possible, because while columns grow linearly, rows grow exponentially, and this violates a growth rate condition on synchronized sequences [ 18 ] . Depending on the choice of f , we can (in some cases) find automata computing the i ’th element of any individual column A_{i,n} . For the arrays we discuss in this paper, it turns out that this is enough! Lemma 2 ensures that there is an an integer n_{0} such that the set S of all values appearing in columns \geq n_{0} are expressible in a simple way from those in column n_{0} , and hence (depending on f ) there can be an automaton accepting S . A similar result holds for all columns of even (resp., odd) index. As we will see, this suffices to prove many existing theorems about the arrays \bf A . For more about Walnut , see [ 16 , 19 ] and the web page https://cs.uwaterloo.ca/~shallit/walnut.html . 4 The experimental approach to Stolarsky interspersions The experimental approach to Stolarsky interspersions involves seven steps. 1. Compute many terms of the first column of the array {\bf A}=(A_{i,j})_{i,j\geq 1} from its definition. In practice, for the arrays we discuss here, 500 to 5000 terms seem sufficient. 2. Use a procedure based on a variation of the Myhill-Nerode theorem to “guess” an automaton M computing a function i\rightarrow A^{\prime}_{i,1} matching the known data; see [ 19 , §5.6] . We now hope that A^{\prime}_{i,1}=A_{i,1} , but of course this has to be rigorously verified! 3. Verify, using Walnut , that M truly does compute a function A^{\prime}_{i,1} (that is, for every i\geq 1 the automaton accepts exactly one input of the form (i,x) ). 4. Verify that A^{\prime}_{i,1} is strictly increasing as a function of i . 5. Compute, using Walnut , an automaton for A^{\prime}_{i,2}=f(A^{\prime}_{i,1}) and A^{\prime}_{i,3}=A^{\prime}_{i,1}+A^{\prime}_{i,2} . 6. From this, using Lemma 2 , compute an automaton accepting the Zeckendorf representations of the set S:=\{A^{\prime}_{i,j}\,:\,i\geq 1,j\geq 3\} . 7. Verify inductively that M is correct by proving that A^{\prime}_{i,1}=\mex(\{A^{\prime}_{i^{\prime},j}\,:\,i^{\prime}=1) => Ex $w1(n,x)": eval w1_func2 "?msd_fib ~En,x,y n>=1 & x!=y & $w1(n,x) & $w1(n,y)": And both return TRUE . Step 4: We verify that w1 computes a strictly increasing function. We do this with eval increasing_w "?msd_fib An,x,y (n>=1 & $w1(n,x) & $w1(n+1,y)) => x=1 & $w3(i,n)": reg all0 msd_fib "0*": concat wcols3 wc3_mem all0: alphabet wcols msd_fib $wcols3: Then we form the automaton for S by also including the values of \{W_{i,2}\,:\,i\geq 1\} . def sw "?msd_fib (Ei i>=1 & $w2(i,n)) | $wcols(n)": Step 7: Now we are poised to prove that the first column computed by w1 is correct, by induction on i . The base case, i=1 , is clear. We use Walnut to check if the “mex” property holds for rows 1,2,\ldots,i-1 , then it also holds for row i . It suffices to show that W_{i,1} is the least number not in T_{i}:=S\,\cup\,\{W_{i^{\prime},1}\,:\,1\leq i^{\prime} n!=x": # checks if x doesn’t appear in set T_i def mex "?msd_fib $chk1(i,x) & Ay (y>=1 & $chk1(i,y)) => y>=x": # check if x is the smallest of all of these eval chk "?msd_fib Ai,x (i>=2 & $mex(i,x)) => $w1(i,x)": And Walnut returns TRUE . We have now (almost) completed the induction proof that w1 correctly computes the array’s first column. However, there is one small technical point. The astute reader will notice that the “mex” result proved her is that W_{i,1} is the least number not in T^{\prime}_{i}:=\{W_{i^{\prime},1}\,:\,1\leq i^{\prime}=1 & $w1(n,z1) & $w2(n,z2)) => $fw(z1,z2)": which returns TRUE . We can also prove closed forms for columns 1 and 2. Proposition 3 . (a) W_{i,1}=\lfloor\alpha^{2}i\rfloor-1 for i\geq 1 . (b) W_{i,2}=2\lfloor\alpha i\rfloor+i-1 for i\geq 1 . Proof. eval prop5a "?msd_fib Ai,x,y (i>=1 & $w1(i,x) & $phi2n(i,y)) => x+1=y": eval prop5b "?msd_fib Ai,x,y (i>=1 & $w2(i,x) & $phin(i,y)) => x+1=2*y+i": ∎ Another property of this array was proven by Morrison [ 15 ] , although its statement as written was imprecise. More precisely stated, it is the following: Theorem 4 . \{W_{i,2}-W_{i,1}\,:\,i\geq 1\}=\{W_{j,2k+1}\,:\,j\geq 1\text{ and }k\geq 0\}. Proof. To prove the theorem, we construct automata testing membership in each set, and then check that they accept exactly the same sets. An automaton for the set on the left is easy to construct: def left "?msd_fib Ei,x,y $w1(i,x) & $w2(i,y) & z+x=y": For the set on the right, we use the fact that (W_{j,\ell})_{F}=(W_{j,3})_{F}0^{\ell-3} for \ell\geq 3 . Thus we can construct the set \{W_{j,2k+1}\,:\,j\geq 1\text{ and }k\geq 0\} as follows: def wc3_memb "?msd_fib Ei i>=1 & $w3(i,n)": reg even0 msd_fib "(00)*": concat w3even wc3_memb even0: alphabet w3e msd_fib $w3even: def right "?msd_fib (Ej j>=1 & $w1(j,n)) | $w3e(n)": And now we check equality: eval checkeq "?msd_fib An (n>=1) => ($left(n) <=> $right(n))": And Walnut returns TRUE . ∎ 6 The Stolarsky array The Stolarsky array [ 22 ] actually predates the Wythoff array, and shares many of the same properties. It is displayed in Table 2 . 1 2 3 4 5 6 7 8 9 10 \cdots 1 1 2 3 5 8 13 21 34 55 89 2 4 6 10 16 26 42 68 110 178 288 3 7 11 18 29 47 76 123 199 322 521 4 9 15 24 39 63 102 165 267 432 699 5 12 19 31 50 81 131 212 343 555 898 6 14 23 37 60 97 157 254 411 665 1076 7 17 28 45 73 118 191 309 500 809 1309 8 20 32 52 84 136 220 356 576 932 1508 9 22 36 58 94 152 246 398 644 1042 1686 10 25 40 65 105 170 275 445 720 1165 1885 \vdots Table 2: The Stolarsky array S_{i,j} . As mentioned before, the function underlying the Stolarsky array is f(n)=\lfloor\alpha n+{1\over 2}\rfloor . Let us carry out the seven steps for this array. Step 1: We can easily compute the first 1000 terms of column 1 from the formula. Step 2: We guess an automaton s1 for it based on this data. Our guessed automaton is s1 and appears in Figure 6 . Figure 6: Guessed automaton for S_{i,1} . Step 3: We verify that s1 actually computes a function. eval s1_func1 "?msd_fib An (n>=1) => Ex $s1(n,x)": eval s1_func2 "?msd_fib ~En,x,y n>=1 & x!=y & $s1(n,x) & $s1(n,y)": Step 4: We verify that s1 is strictly increasing. eval increasing_s "?msd_fib An,x,y (n>=1 & $s1(n,x) & $s1(n+1,y)) => x=1 & $s2(i,n)": reg all0 msd_fib "0*": concat scol sc2_mem all0: alphabet scols msd_fib $scol: def chks1 "?msd_fib (~$scols(n)) & Aj,x (j n!=x": def mexs "?msd_fib $chks1(i,x) & Ay (y>=1 & $chks1(i,y)) => y>=x": eval chks2 "?msd_fib Ai,x (i>=2 & $mexs(i,x)) => $s1(i,x)": It now follows that our guess for S_{i,1} was correct. As an application, we can find simple expressions for the first and second columns: Theorem 5 . We have S_{n,1}=\lfloor n\alpha^{2}-\alpha/2\rfloor for n\geq 1 . Proof. Simple manipulation shows \lfloor n\alpha^{2}-\alpha/2\rfloor=n+\left\lfloor{{\lfloor(2n-1)\alpha\rfloor}\over 2}\right\rfloor. So we can prove Theorem 5 as follows: eval thms1 "?msd_fib An,x (n>=1) => ($s1(n,x) <=> Ey,z $phin(2*n-1,y) & z=y/2 & x=z+n)": ∎ Theorem 6 . We have S_{n,2}=\lfloor n(\sqrt{5}+2)-\alpha\rfloor for n\geq 1 . Proof. Since \sqrt{5}+2=2\alpha+1 , we can prove the theorem as follows: eval thms2 "?msd_fib An,x (n>=1) => ($s2(n,x) <=> Ey $phin(2*n-1,y) & x=y+n)": ∎ Stolarsky conjectured that S_{n,2}-S_{n,1}\in\{S_{i,1}\,:\,1\leq i=2 & $s1(n,x) & $s2(n,y)) => Ei,a,b 1<=i & i=1 & Ex,y,i,a 1<=i & i=1) => ((Ei,x,y,z $s1(n,x) & $s2(n,y) & $s1(i,z) & y=x+z) <=> (Ek,t $phin(2*k-1,t) & n=t/2+1))": And Walnut returns TRUE . ∎ Let us use this approach to solve a problem of Kimberling [ 9 ] . Given a Stolarsky interspersion (A_{i,j})_{i,j\geq 1} , he defined the classification sequence \delta_{i}:=A_{i,2}-\lfloor\alpha A_{i,1}\rfloor , and proved that \delta_{i}\in\{0,1\} . Some arrays, such as the Wythoff array, have very simple classification sequences; for the Wythoff array it is \delta_{i}=1 . Kimberling asked for a “convenient formula” for the classification sequence \delta_{i} for the Stolarsky array \bf s . Using Walnut , and automata for the first two columns of a Stolarsky interspersion, we can easily compute an automaton for the classification sequence (\delta_{i})_{i\geq 1} . def delta "?msd_fib Ex,y,z $s1(n,x) & $phin(x,y) & $s2(n,z) & z=y": It is depicted in Figure 7 . Figure 7: Automaton for (\delta_{i})_{i\geq 1} . Of course, some would object to an automaton proffered as a “convenient formula”. Nevertheless, once we have the automaton, we can efficiently compute an arbitrary term of the sequence \delta_{i} . Let us take an experimental approach to determining another kind of formula for (\delta_{i})_{i\geq 1} . For example, we can look at the frequency of occurrences of the symbol 1 in the first n terms of (\delta_{i})_{i\geq 1} , and we discover it seems to be 1/2 . This is reminiscent of a Rote sequence [ 17 ] , so it suggests verifying this by computing subword complexity of the sequence, where subword complexity is the function mapping n to the number of distinct length- n blocks occurring in the sequence. The empirical data suggests the subword complexity is 2n for n\geq 1 , which confirms the possibility of (\delta_{i})_{i\geq 1} as a Rote sequence. This, in turn, suggests that perhaps \delta_{i}=1 if and only if \{\alpha n+\rho\}\in[0,\kappa) for some numbers \rho,\gamma . An experimental approach now tries pairs (\rho,\gamma) generated at random and seeing how close the resulting sequence is to (\delta_{i})_{i\geq 1} . We quickly converge on the candidates \rho=1/2,\gamma=(3-\alpha)/2 . Once we have this guess, we can verify it using Walnut : def l1 "?msd_fib Ex $phin(2*n-1,x) & z=(x+3)/2": # automaton computing floor(gamma + g*n) def l2 "?msd_fib Ex $phin(2*n-1,x) & z=(x/2)+2": # automaton computing floor(gamma+ g*n + 1/2) def l3 "?msd_fib Ex,y $l1(n,x) & $l2(n,y) & x=y": # automaton deciding if fractional part of gamma+g*n < 1/2 eval tmp "?msd_fib An (n>=1) => ($l3(n) <=> $delta(n,1))": # check they are the same, result is TRUE We have now proved the following new result, which offers an answer to Kimberling’s question. Theorem 8 . Let \gamma=(3-\alpha)/2 . We have \delta_{i}=\begin{cases}1,&\text{if $\{\alpha n+{1\over 2}\}\in[0,\gamma)$};\\ 0,&otherwise.\end{cases} 7 The dual Wythoff array The dual Wythoff array {\bf D}=(D_{i,j})_{i,j\geq 1} was introduced by Kimberling [ 9 , p. 314] . It corresponds to the case f(n)=\lfloor\alpha n+\beta^{2}\rfloor , although Kimberling did not define it like that. The first few rows and columns are given in Table 3 . 1 2 3 4 5 6 7 8 9 10 \cdots 1 1 2 3 5 8 13 21 34 55 89 2 4 6 10 16 26 42 68 110 178 288 3 7 11 18 29 47 76 123 199 322 521 4 9 14 23 37 60 97 157 254 411 665 5 12 19 31 50 81 131 212 343 555 898 6 15 24 39 63 102 165 267 432 699 1131 7 17 27 44 71 115 186 301 487 788 1275 8 20 32 52 84 136 220 356 576 932 1508 9 22 35 57 92 149 241 390 631 1021 1652 10 25 40 65 105 170 275 445 720 1165 1885 \vdots Table 3: The dual Wythoff array D_{i,j} . We can prove properties of this array just like we did with Stolarsky’s array. Step 1: We compute the first 1000 entries of column 1 using f(n)=\lfloor\alpha n+\beta^{2} . Step 2: We guess an automaton d1 for the first column from empirical data. It has 11 states and is depicted in Figure 8 . Figure 8: Guessed automaton for D_{i,1} . Step 3: We verify that d1 computes a function. eval d1_func1 "?msd_fib An (n>=1) => Ex $d1(n,x)": eval d1_func2 "?msd_fib ~En,x,y n>=1 & x!=y & $d1(n,x) & $d1(n,y)": Step 4: We verify that d1 is strictly increasing. eval increasing_d "?msd_fib An,x,y (n>=1 & $d1(n,x) & $d1(n+1,y)) => x=1 & $d3(i,n)": reg all0 msd_fib "0*": concat dcol dc3_mem all0: alphabet dcols msd_fib $dcol: def dw "?msd_fib (Ei i>=1 & $d2(i,n)) | $dcols(n)": Step 7: We prove the induction step that the ‘mex’ property holds for the array D . def chkd1 "?msd_fib (~$dw(n)) & Aj,x (j n!=x": def mexd "?msd_fib $chkd1(i,x) & Ay (y>=1 & $chkd1(i,y)) => y>=x": eval chkd2 "?msd_fib Ai,x (i>=2 & $mexd(i,x)) => $d1(i,x)": Now we know that the automaton d1 indeed computes the first column correctly. Furthermore we can find a closed form for it. Theorem 9 . We have D_{i,1}=\lceil\alpha^{2}i-\alpha\rceil . Proof. It suffices to prove that D_{i,1}=\lfloor\alpha^{2}i-\alpha\rfloor+1 for i\geq 2 . Note that \lfloor\alpha^{2}i-\alpha\rfloor=\lfloor(\alpha+1)i-\alpha\rfloor=i+\lfloor\alpha(i-1)\rfloor . eval chkd1 "?msd_fib Ai,x,y (i>=2 & $d1(i,x) & $phin(i-1,y)) => x=y+i+1": ∎ Kimberling used a different description of the array. We now prove his description is equivalent to ours. Theorem 10 . (a) The classification sequence \delta_{i} for the dual Wythoff array is given by \delta_{1}=1 and \delta_{i}=0 for all i\geq 2 . (b) We have D_{i,1}=\begin{cases}\lfloor i\alpha\rfloor+i,&\text{if there exists $k\geq 1$ such that $i=\lfloor k\alpha\rfloor+k+1$ };\\ \lfloor i\alpha\rfloor+i-1,&\text{otherwise.}\end{cases} Proof. def delta "?msd_fib Ex,y,t $d1(i,x) & $d2(i,y) & $phin(x,t) & z+t=y": eval checka "?msd_fib Ai (i>=2) => $delta(i,0)": def cond "?msd_fib Ek,x k>=1 & $phin(k,x) & i=x+k+1": def d1_alt "?msd_fib ($cond(i) & Ex $phin(i,x) & z=x+i) | (~$cond(i) & Ex $phin(i,x) & z+1=x+i)": eval checkb "?msd_fib Ai,x,y (i>=1 & $d1(i,x) & $d1_alt(i,y)) => x=y": ∎ 8 More general interspersions Up to now the second column of the arrays we study has been a function only of the values appearing in the first column. Now we consider a more general case where the entries in the second column A_{i,2} are functions of the first column and index, as follows: A_{i,2}=\lfloor\alpha A_{i,1}\rfloor+\delta_{i} . Here \delta_{i} is the so-called classification sequence of Kimberling [ 9 ] . 8.1 The EFC array Kimberling defined an array, which he called the EFC array ( e ven f irst c olumn), as follows: {\bf E}=(E_{i,j})_{i,j\geq 1} with classification sequence defined by \delta_{1}=1 and \delta_{2k}=1 , \delta_{2k+1}=0 for all k\geq 1 . The first few rows and columns are given in Table 4 . 1 2 3 4 5 6 7 8 9 10 \cdots 1 1 2 3 5 8 13 21 34 55 89 2 4 7 11 18 29 47 76 123 199 322 3 6 9 15 24 39 63 102 165 267 432 4 10 17 27 44 71 115 186 301 487 788 5 12 19 31 50 81 131 212 343 555 898 6 14 23 37 60 97 157 254 411 665 1076 7 16 25 41 66 107 173 280 453 733 1186 8 20 33 53 86 139 225 364 589 953 1542 9 22 35 57 92 149 241 390 631 1021 1652 10 26 43 69 112 181 293 474 767 1241 2008 \vdots Table 4: The EFC array E_{i,j} . With this definition, Kimberling gave an explicit characterization of the first column E_{2n,1} . However, his proof was rather complicated, consisting of three pages and six cases. We can handle this rather easily using our experimental approach. Step 1: we compute the first 1000 terms of the first column of the EFC array. Step 2: We guess an automaton efc1 for the first column from the data; it has 33 states, too big to display here. Step 3: We verify that efc1 computes a function. eval efc1_func1 "?msd_fib An (n>=1) => Ex $efc1(n,x)": eval efc1_func2 "?msd_fib ~En,x,y n>=1 & x!=y & $efc1(n,x) & $efc1(n,y)": Step 4: We verify that the function computed by efc1 is increasing. eval increasing_efc "?msd_fib An,x,y (n>=1 & $efc1(n,x) & $efc1(n+1,y)) => x=2 & Ex,y,k,r $efc1(i,x) & $phin(x,y) & i=2*k+r & r<=1 & z=y+(1-r))": def efc3 "?msd_fib Ex,y $efc1(i,x) & $efc2(i,y) & z=x+y": These have 47 and 67 states, respectively. Step 6: We compute the set S . def efcg3 "?msd_fib Ei i>=1 & $efc3(i,n)": reg all0 msd_fib "0*": concat efc_zero3 efcg3 all0: alphabet efc_cols3 msd_fib $efc_zero3: def efc_cols2 "?msd_fib (Em m>=1 & $efc2(m,n))|$efc_cols3(n)": Step 7: We check the ‘mex’ property. def chk_efc1 "?msd_fib (~$efc_cols2(n)) & Aj,x (j n!=x": def mex_efc "?msd_fib $chk_efc1(i,x) & Ay (y>=1 & $chk_efc1(i,y)) => y>=x": eval chk_efc "?msd_fib Ai,x (i>=2 & $mex_efc(i,x)) => $efc1(i,x)": and Walnut returns TRUE . Now that we know the array is correct, we can prove Kimberling’s characterization of column 1: Theorem 11 . For n\geq 1 we have \displaystyle E_{2n,1} \displaystyle=2\lfloor n\alpha\rfloor+2n; \displaystyle E_{2n+1,1} \displaystyle=2\lfloor n\alpha\rfloor+2n+2. Hence E_{2n,1} is even for all n\geq 2 . Proof. eval efc_even "?msd_fib An,x,y (n>=1 & $efc1(2*n,x) & $phin(n,y)) => x=2*y+2*n": eval efc_odd "?msd_fib An,x,y (n>=1 & $efc1(2*n+1,x) & $phin(n,y)) => x=2*y+2*n+2": ∎ 8.2 The ESC array Kimberling [ 9 ] defined a Stolarsky interspersion where \delta_{i}=i\bmod 2 for i\geq 1 ; he called the resulting array “ESC” ( e ven s econd c olumn); We will denote it as (E^{\prime}_{i,j})_{i,j\geq 1} . He conjectured that with this choice of \delta , the second column is always even, a fact later proved by Behrend [ 1 ] . We can reprove this result and also determine a closed form for the second column sequence. Step 1: We compute 1000 terms of the first column from the definition. Step 2: We deduce an automaton esc1 that we hope is correct for E^{\prime}_{i,1} . It has 39 states. We do not display it here because it is too large. Step 3: We verify that esc1 represents a function. eval esc1_func1 "?msd_fib An (n>=1) => Ex $esc1(n,x)": eval esc1_func2 "?msd_fib ~En,x,y n>=1 & x!=y & $esc1(n,x) & $esc1(n,y)": Step 4: We verify that the function computed is increasing. eval increasing_esc "?msd_fib An,x,y (n>=1 & $esc1(n,x) & $esc1(n+1,y)) => x=1 & $esc3(i,n)": reg all0 msd_fib "0*": concat esc_zero3 escg3 all0: alphabet esc_cols3 msd_fib $esc_zero3: def esc_cols2 "?msd_fib (Em m>=1 & $esc2(m,n))|$esc_cols3(n)": Step 7: We check the ‘mex’ property. def chk_esc1 "?msd_fib (~$esc_cols2(n)) & Aj,x (j n!=x": def mex_esc "?msd_fib $chk_esc1(i,x) & Ay (y>=1 & $chk_esc1(i,y)) => y>=x": eval chk_esc "?msd_fib Ai,x (i>=2 & $mex_esc(i,x)) => $esc1(i,x)": Finally we can check the assertion that the second column is always even, as follows: eval tmp "?msd_fib Ai,x (i>=1 & $esc2(i,x)) => Ek x=2*k": 9 Final remarks In principle, one can use this method to compute automata and prove theorems about Stolarsky interspersions based on other functions f and other classification sequences. However, currently we have no proof that, for example, there will always be an automaton for the first column of a Stolarsky interspersion with periodic classification sequence \delta_{i} , nor a direct way to compute the automaton from \delta_{i} without “guessing”. We also do not know how the number of states grows with the period of the periodic sequence. It would be interesting to try to prove something about this. For example, for the classification sequence defined by \delta_{i}=1 if i\equiv 1 (mod 3 ), and 0 otherwise, we can get an automaton k100 for the first column sequence 1,4,7,9,12,14,17,20,23,25,27,30,33,35,38,40,44,46,49,\ldots with 87 states. With our method we can prove, for example, the following result: Theorem 12 . The Stolarsky array with classification sequence 1,0,0,1,0,0,1,0,0,\ldots has a third column with terms that are only 0,1 (mod 3 ), never 2 (mod 3 ). Proof. We verify our guess and the property. The Walnut code is given without commentary, as it is just the same in spirit as before. eval k100_func1 "?msd_fib An (n>=1) => Ex $k100(n,x)": eval k100_func2 "?msd_fib ~En,x,y n>=1 & x!=y & $k100(n,x) & $k100(n,y)": eval increasing_k100 "?msd_fib An,x,y (n>=1 & $k100(n,x) & $k100(n+1,y)) => x=1 & $k1003(i,n)": reg all0 msd_fib "0*": concat k100_zero3 k100g3 all0: alphabet k100_cols3 msd_fib $k100_zero3: def k100_cols2 "?msd_fib (Em m>=1 & $k1002(m,n))|$k100_cols3(n)": def chk_k100 "?msd_fib (~$k100_cols2(n)) & Aj,x (j n!=x": def mex_k100 "?msd_fib $chk_k100(i,x) & Ay (y>=1 & $chk_k100(i,y)) => y>=x": eval chk_k100 "?msd_fib Ai,x (i>=2 & $mex_k100(i,x)) => $k100(i,x)": eval col3 "?msd_fib Ai,x (i>=1 & $k1003(i,x)) => ~Ek x=3*k+2": And Walnut returns TRUE . ∎ One thing I do not currently know how to do is use these kinds of methods to discuss the so-called “row sequence”, which is sequence r_{n} defined by the row number in which n in appears, say, in the Wythoff array. I do not see a way to study this sequence using automata theory. One can object that, for example, for the ESC array, we have only verified that the second column is always even, but we have not explained why. This raises the question of what would be considered a satisfying answer. Evidently a simple formula of the form \lfloor\gamma n+\rho\rfloor for some irrationals \gamma,\rho would be acceptable, but subword complexity shows that no such formula can work here. We would need something more complicated. Perhaps the 39-state automaton for esc1 is going to be the simplest “formula” we can find. We note that Behrend did not prove any kind of simple formula for the second column of ESC , either.