A317948 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.

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, 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, 2, 0, 2, 3, 1, 0, 1, 2, 3, 0, 0, 2, 3, 1, 0, 1, 2, 3, 0

Offset: 1

Author

N. J. A. Sloane, Aug 12 2018

Keywords

• nonn
• tabl

Comments

The Duchêne et al. (2011) reference mentions many other sequences that are of great interest.

From Kevin Ryde, Dec 26 2020: (Start)

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.

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.

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.

(End)

Examples

			From _Kevin Ryde_, Dec 26 2020: (Start)
Array S(m,k) begins
       k=0  1  2  3  4  5  6  7
      +-------------------------
  m=0 |  0, 0, 0, 0, 0, 0, 0, 0,
  m=1 |  1, 3, 2, 1, 3, 2, 1,
  m=2 |  2, 1, 3, 2, 1, 3,     sequence by upwards
  m=3 |  3, 2, 1, 3, 2,          antidiagonals,
  m=4 |  0, 0, 0, 0,
  m=5 |  1, 3, 2,          12-periodic in diagonals
  m=6 |  2, 1,             (3 or 1-periodic in rows)
  m=7 |  3,                 (4-periodic in columns)
(End)
		

Links

• Eric Duchêne, Aviezri S. Fraenkel, Richard J. Nowakowski, and Michel Rigo, Extensions and restrictions of Wythoff's game preserving Wythoff's sequence as set of P-positions, 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...".
• Michel Rigo, Generalization of automatic sequences for numeration systems on a regular language, Theoret. Comput. Sci., 244 (2000) 271-281. See section 2.1 sequence u.
• Michel Rigo and Arnaud Maes, More on generalized automatic sequences, Journal of Automata, Languages and Combinatorics 7.3 (2002): 351-376. See Fig. 3.

Programs

PARI

S(m,k) = if(m%=4, (m-k-1)%3+1, 0); \\ Kevin Ryde, Dec 26 2020

Python

aut0, aut1 = [1, 2, 3, 0], [0, 3, 1, 2]
a, row = [0], [0]
for i in range(1, 10):
    row = [aut0[row[0]]] + [aut1[x] for x in row]
    a += row
print(a)
# Andrey Zabolotskiy, Aug 17 2018

Formula

From Kevin Ryde, Dec 26 2020: (Start)

S(m,k) = 0 if m==0 (mod 4), otherwise S(m,k) = (((m mod 4) - k - 1) mod 3) + 1.

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.

(End)

Extensions

New name and terms a(51) and beyond from Andrey Zabolotskiy, Aug 17 2018