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,4

Comments

a(n) = DC(w[n]), where w[n] is the n-th binary string in shortlex order: 0, 1, 00, 01, 10, 11, 000, 001, .... (row n-1 of A076478).

The Deterministic Complexity (DC) of a string w is the minimum number of states in a deterministic Mealy automaton outputting the string w. Alternatively, DC(w) = |u|+|v| for the smallest (possibly empty) u and primitive word v, such that w = trunc(uv^k,|w|) for some k >= 1, where trunc(x,L) truncates the word x to length L.

1..L each appear at least twice in row L since DC(0^i 1^(L-i)) = DC(1^i 0^(L-i)) = i+1 for i = 0..L-1. - Michael S. Branicky, Mar 03 2024

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

Example

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.

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)}]]

Prog

(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

Crossrefs

Cf. A059412, A076478, A370821.

Sequence in context: A139767 A207822 A343068 * A057555 A075532 A050176

Adjacent sequences: A370486 A370487 A370488 * A370490 A370491 A370492

Keyword

nonn,tabf

Author

Lucas B. Vieira, Mar 02 2024

Status

approved