A370489 - OEIS

%I #62 Mar 07 2024 14:52:37

%S 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,

%T 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,

%U 5,4,4,3,3,5,4,4,5,3,3,4,3,5,5,2

%N Deterministic complexity of binary strings, in shortlex order.

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

%C 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.

%C 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

%H Michael S. Branicky, <a href="/A370489/b370489.txt">Table of n, a(n) for n = 1..10000</a>

%H Lucas B. Vieira and Costantino Budroni, <a href="https://doi.org/10.22331/q-2022-01-18-623">Temporal correlations in the simplest measurement sequences</a>, Quantum 6 p. 623 (2022).

%e 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.

%e 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.

%t (* e.g. DC[{0,0,1,0,1}] = 3 *)

%t 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}]];

%t a[n_] := DC[Rest[IntegerDigits[n + 1, 2]]];

%t (* Table for all sequences up to length 10 *)

%t With[{L = 10}, Table[a[n], {n, 2*(2^L-1)}]]

%o (Python)

%o 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)])

%o def a(n): return DC(bin(n+1)[3:])

%o print([a(n) for n in range(1, 88)]) # _Michael S. Branicky_, Mar 03 2024

%Y Cf. A059412, A076478, A370821.

%K nonn,tabf

%O 1,4

%A _Lucas B. Vieira_, Mar 02 2024