A347198 Consider the sequence of binary words of integers, LSB to MSB S(k) = ( 0; 1; 01; 11; 001; 101; 011; ... ). Start with a(0) = 0, extend this sequence with the minimum number of [0;1] such that it contains S(1) then S(2) and so forth, as sub-strings with LSB at any a(n). We extend the sequence as much as required to include S(k) first, in the next step we extend until it includes S(k+1) too.

0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1

Offset

0

Comments

It appears that in the long term the mean of this sequence is 1/2.

This sequence is disjunctive but not normal. This means every finite string appears as a substring. But not each string of equal length appears with equal frequency. Compare to A076478 which is known to be disjunctive and normal.

An interesting problem: If we choose an interval a(0);...;a(n) such that this subsequence contains all binary words of 0;1;2;...;k for given k, for which k will this subsequence have the shortest possible length required to obtain this property. Trivial examples would be n = 1 (k = 2): 01 -> 0;1;01 and n = 2 (k = 3): 011 -> 0;1;01;11. This would require n <= floor(log_2(A056744(k)) + 1).

Links

Michael S. Branicky, Table of n, a(n) for n = 0..10000

Cristian S. Calude, Lutz Priese and Ludwig Staiger, Disjunctive sequences: An overview, University of Auckland, New Zealand (1997).

Thomas Scheuerle, Sum_{k=0..n}(1-2*a(k)) for n from 0 to 100000. Shows some self-similarity.

Example

Actual sequence:  Next desired binary word:  Required extension:
0                 1                          1
01                01                         none
01                11                         1
011               001                        001
011001            101                        01
01100101          011                        none
01100101          111                        11

Prog

(MATLAB)
function a = A347198( max_n )
a = 0; m = 1;
    while length(a) < max_n
      b = bitget(m, 1:64);
      word = b(1:find(b == 1, 1, 'last' ));
      if isempty(strfind(a, word))
          offset = 0;
          max_o = min(length(word), length(a));
          for o = 1:max_o
              if  isequal(a(end-(o-1):end), word(1:o))
                  offset = o;
              end
          end
          a = [a word(1+offset:end)];
      end
      m = m+1;
    end
end
(Python)
from itertools import count, islice
def a(): # generator of terms
    S = ""
    for k in count(0):
        Sk = bin(k)[2:][::-1]
        if Sk in S: continue
        for i in range(1, len(Sk)+1):
            v = Sk[-i:]
            t = "" if len(v) == len(Sk) else S[-len(Sk)+i:]
            if t+v == Sk: break
        S += v
        yield from list(map(int, v))
print(list(islice(a(), 105))) # Michael S. Branicky, Oct 27 2023

Crossrefs

Cf. A056744, A076478, A108737.

Sequence in context: A327974 A286049 A287657 * A079336 A288670 A057215

Adjacent sequences: A347195 A347196 A347197 * A347199 A347200 A347201

Keyword

base,nonn

Author

Thomas Scheuerle, Aug 22 2021

Extensions

a(26)-a(27) corrected and more terms from Michael S. Branicky, Oct 27 2023

Status

approved