%I #52 Oct 28 2023 05:43:15
%S 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,
%T 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,
%U 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
%N 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.
%C It appears that in the long term the mean of this sequence is 1/2.
%C 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.
%C 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).
%H Michael S. Branicky, <a href="/A347198/b347198.txt">Table of n, a(n) for n = 0..10000</a>
%H Cristian S. Calude, Lutz Priese and Ludwig Staiger, <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1370">Disjunctive sequences: An overview</a>, University of Auckland, New Zealand (1997).
%H Thomas Scheuerle, <a href="/A347198/a347198_1.svg">Sum_{k=0..n}(1-2*a(k)) for n from 0 to 100000. Shows some self-similarity.</a>
%e Actual sequence: Next desired binary word: Required extension:
%e 0 1 1
%e 01 01 none
%e 01 11 1
%e 011 001 001
%e 011001 101 01
%e 01100101 011 none
%e 01100101 111 11
%o (MATLAB)
%o function a = A347198( max_n )
%o a = 0; m = 1;
%o while length(a) < max_n
%o b = bitget(m,1:64);
%o word = b(1:find(b == 1, 1, 'last' ));
%o if isempty(strfind(a, word))
%o offset = 0;
%o max_o = min(length(word),length(a));
%o for o = 1:max_o
%o if isequal(a(end-(o-1):end),word(1:o))
%o offset = o;
%o end
%o end
%o a = [a word(1+offset:end)];
%o end
%o m = m+1;
%o end
%o end
%o (Python)
%o from itertools import count, islice
%o def a(): # generator of terms
%o S = ""
%o for k in count(0):
%o Sk = bin(k)[2:][::-1]
%o if Sk in S: continue
%o for i in range(1, len(Sk)+1):
%o v = Sk[-i:]
%o t = "" if len(v) == len(Sk) else S[-len(Sk)+i:]
%o if t+v == Sk: break
%o S += v
%o yield from list(map(int, v))
%o print(list(islice(a(), 105))) # _Michael S. Branicky_, Oct 27 2023
%Y Cf. A056744, A076478, A108737.
%K base,nonn
%O 0
%A _Thomas Scheuerle_, Aug 22 2021
%E a(26)-a(27) corrected and more terms from _Michael S. Branicky_, Oct 27 2023
|