A317948 - OEIS

%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