|
| |
|
|
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.
|
|
1
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
The Duchêne et al. (2011) reference mentions many other sequences that are of great interest.
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)
|
|
|
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...".
|
|
|
FORMULA
|
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)
|
|
|
EXAMPLE
|
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)
|
|
|
PROG
|
(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)
(PARI) S(m, k) = if(m%=4, (m-k-1)%3+1, 0); \\ Kevin Ryde, Dec 26 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
