|
%I #41 Feb 01 2021 02:18:43
%S 0,1,0,2,3,0,3,1,2,0,0,2,3,1,0,1,0,1,2,3,0,2,3,0,3,1,2,0,3,1,2,0,2,3,
%T 1,0,0,2,3,1,0,1,2,3,0,1,0,1,2,3,0,3,1,2,0,2,3,0,3,1,2,0,2,3,1,0,3,1,
%U 2,0,2,3,1,0,1,2,3,0,0,2,3,1,0,1,2,3,0
%N An example of a morphic word: the sorted (by length, then alphabetically) sequence of words of the form a*b* under the action of a finite automaton defined as follows: start state is 0; a and b map states [0, 1, 2, 3] to states [1, 2, 3, 0] and [0, 3, 1, 2], respectively.
%C The Duchêne et al. (2011) reference mentions many other sequences that are of great interest.
%C From _Kevin Ryde_, Dec 26 2020: (Start)
%C This sequence can be taken as a square array S(m,k) read by upwards antidiagonals with rows m >= 0 and columns k >= 0. S(m,k) is the final state for input word a^m b^k where ^ denotes repetition. Input a's cycle around states 0,1,2,3 so S(m,0) = m mod 4. Within an array row, input b's are no change at state 0 (so a row of 0's), or a repeating cycle 3,2,1 starting at m mod 4.
%C Antidiagonal d of the array is input words of length d = m+k, so terms S(d-k,k). These are words a^(d-k) b^k and the combination of d-k mod 4 and k mod 3 is 12-periodic within a diagonal. The sequence can also be taken as a triangle read by rows T(d,k) = S(d-k,k) for d >= 0 and 0 <= k <= d.
%C Rigo (2000, section 2.1 remark 2) notes that the sequence (flat sequence) is not periodic because pairs of terms 0,0 are at ever-increasing distances apart. They are a(n)=a(n+1)=0 iff n = 2*t*(4*t+1) = A033585(t) for t >= 1, which is every fourth triangular number.
%C (End)
%H Eric Duchêne, Aviezri S. Fraenkel, Richard J. Nowakowski, and Michel Rigo, <a href="https://orbi.uliege.be/handle/2268/100440">Extensions and restrictions of Wythoff's game preserving Wythoff's sequence as set of P-positions</a>, Slides from a talk, LIAFA, Paris, October 21, 2011. See around the 35th slide, a slide with first line "In fact, this is a special case of the following result...".
%H Michel Rigo, <a href="https://doi.org/10.1016/S0304-3975(00)00163-8">Generalization of automatic sequences for numeration systems on a regular language</a>, Theoret. Comput. Sci., 244 (2000) 271-281. See section 2.1 sequence u.
%H Michel Rigo and Arnaud Maes, <a href="https://www.jalc.de/issues/2002/issue_7_3/abs-351.pdf">More on generalized automatic sequences</a>, Journal of Automata, Languages and Combinatorics 7.3 (2002): 351-376. See Fig. 3.
%F From _Kevin Ryde_, Dec 26 2020: (Start)
%F S(m,k) = 0 if m==0 (mod 4), otherwise S(m,k) = (((m mod 4) - k - 1) mod 3) + 1.
%F T(d,k) = S(d-k,k) = p(3*d+k mod 12) where p(0..11) = 0,2,3,1, 0,1,2,3, 0,3,1,2.
%F (End)
%e From _Kevin Ryde_, Dec 26 2020: (Start)
%e Array S(m,k) begins
%e k=0 1 2 3 4 5 6 7
%e +-------------------------
%e m=0 | 0, 0, 0, 0, 0, 0, 0, 0,
%e m=1 | 1, 3, 2, 1, 3, 2, 1,
%e m=2 | 2, 1, 3, 2, 1, 3, sequence by upwards
%e m=3 | 3, 2, 1, 3, 2, antidiagonals,
%e m=4 | 0, 0, 0, 0,
%e m=5 | 1, 3, 2, 12-periodic in diagonals
%e m=6 | 2, 1, (3 or 1-periodic in rows)
%e m=7 | 3, (4-periodic in columns)
%e (End)
%o (Python)
%o aut0, aut1 = [1, 2, 3, 0], [0, 3, 1, 2]
%o a, row = [0], [0]
%o for i in range(1, 10):
%o row = [aut0[row[0]]] + [aut1[x] for x in row]
%o a += row
%o print(a)
%o # _Andrey Zabolotskiy_, Aug 17 2018
%o (PARI) S(m,k) = if(m%=4, (m-k-1)%3+1, 0); \\ _Kevin Ryde_, Dec 26 2020
%K nonn,tabl
%O 1,4
%A _N. J. A. Sloane_, Aug 12 2018
%E New name and terms a(51) and beyond from _Andrey Zabolotskiy_, Aug 17 2018
|
