A370489 Deterministic complexity of binary strings, in shortlex order.
1, 1, 1, 2, 2, 1, 1, 3, 2, 2, 2, 2, 3, 1, 1, 4, 3, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 3, 4, 1, 1, 5, 4, 4, 3, 3, 4, 3, 3, 3, 2, 4, 4, 3, 4, 2, 2, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 1, 1, 6, 5, 5, 4, 4, 5, 4, 4, 3, 3, 5, 4, 4, 5, 3, 3, 4, 3, 5, 5, 2
Offset: 1
Examples
For n = 1, w[1] = 0, and DC(w[1]) = 1. The minimal deterministic Mealy automaton outputting w[1] has a single state, transitioning to itself and outputting 0. For n = 36, w[36] = 00101, and DC(w[36]) = 3. The minimal deterministic Mealy automaton has 3 states: transitions 1->2 and 2->3 output 0, and 3->2 outputs 1.
Links
- Michael S. Branicky, Table of n, a(n) for n = 1..10000
- Lucas B. Vieira and Costantino Budroni, Temporal correlations in the simplest measurement sequences, Quantum 6 p. 623 (2022).
Programs
-
Mathematica
(* e.g. DC[{0,0,1,0,1}] = 3 *) DC[seq_] := With[{L = Length[seq]}, Do[If[With[{c = dc - t}, Take[Flatten[{Take[seq, t], ConstantArray[Take[Drop[seq, t], c], Ceiling[(L - t)/c]]}], L]] == seq, Return[dc]], {dc, 0, L}, {t, 0, dc - 1}]]; a[n_] := DC[Rest[IntegerDigits[n + 1, 2]]]; (* Table for all sequences up to length 10 *) With[{L = 10}, Table[a[n], {n, 2*(2^L-1)}]] -
Python
def DC(w): return next(dc for dc in range(1, len(w)+1) for i in range(dc) if w == (w[:i]+w[i:dc]*(1+(len(w)-i)//(dc-i)))[:len(w)]) def a(n): return DC(bin(n+1)[3:]) print([a(n) for n in range(1, 88)]) # Michael S. Branicky, Mar 03 2024
Comments