OFFSET
1,1
COMMENTS
From Andrei Zabolotskii, Oct 07 2025: (Start)
The n-th transducer in question is a certain directed graph, denoted by Rao as T^n. It has 2^n vertices, labeled by the strings of 1's and 2's of length n. Each edge has two labels: an input label and an output label. Each vertex has two outgoing edges having input labels 1 and 2.
The output label of an edge is the n-th string, s_n, from a sequence of strings of 1's and 2's, s_k, such that s_0 is the input label, while for 0 < k <= n, s_{k-1} is the run-length transform of s_k and the first symbol in s_k is the k-th symbol of the source vertex. The target vertex is defined by the condition that the k-th symbol of its label is different from the last symbol of s_k.
For example, in T^4, consider the vertex 2221 and its outgoing edge with the input label s_0 = 1. Then s_1 = 2, s_2 = 22, s_3 = 2211, the output label is s_4 = 112212, and the target vertex is 1121.
For any n, if we start in T^n at the vertex of all 1's and follow the path such that the input labels of the edges form the Kolakoski sequence, the concatenation of the output labels will be the Kolakoski sequence again. (End)
LINKS
Michael Rao, Trucs et bidules sur la séquence de Kolakoski, October 1 2012.
EXAMPLE
In Rao's graph T^4, there is a cycle 1121 -> 2212 -> 1112 -> 2221 -> 1121, in which the edges have output labels 11, 212211, 2, 112212. Out of 15 symbols in these labels, 8 symbols are 1's. The fraction of 1's, 8/15, is maximal over all cycles in T^4, and this cycle has 4 edges. Thus, a(4) = 4.
PROG
(SageMath)
def lbl(x):
return tuple(lbl(y) for y in x) if isinstance(x, tuple) \
else dict(lbl(y) for y in x.items()) if isinstance(x, dict) \
else lbl(x.label()) if hasattr(x, 'label') \
else x[2::2] if isinstance(x, str) else x
def f1(d, cyc):
s = ''.join(d[e1][e2] for e1, e2 in zip(cyc, cyc[1:]))
return Rational((s.count('1'), len(s)))
t = t1 = Transducer([(1, 2, 1, 1), (1, 2, 2, [1, 1]), (2, 1, 1, 2), (2, 1, 2, [2, 2])], initial_states=[1, 2], final_states=[1, 2])
for n in (1..5):
if n == 1: a = 2
else:
t = t1.composition(t)
d = lbl(t.digraph().to_dictionary(edge_labels=True))
a = len(max(DiGraph(d).all_simple_cycles(), key = lambda cyc: f1(d, cyc))) - 1
print(a) # Andrei Zabolotskii, Oct 04 2025
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Feb 08 2019
EXTENSIONS
Name edited by Andrei Zabolotskii, Oct 04 2025
STATUS
approved