A108736 - OEIS

%I #14 Oct 27 2023 13:10:12

%S 0,1,0,0,1,1,0,0,0,1,0,1,1,1,0,0,0,0,1,0,1,0,1,1,0,1,1,1,1,0,0,0,0,0,

%T 1,1,0,0,1,0,0,1,1,1,0,1,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1,0,1,

%U 0,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,0,1,1,0,1,0,1,1,0,1,1,0,1,1,1,0

%N Start with S = {}. For m = 1, 2, 3, ... in turn, examine all 2^m m-bit strings u in arithmetic order. If u is not a substring of S, append the minimal number of 0's and 1's to S to remedy this. Sequence gives S.

%H Michael S. Branicky, <a href="/A108736/b108736.txt">Table of n, a(n) for n = 1..10001</a>

%e We construct S as follows, starting with S = {}.

%e 0 is missing, so S = {0};

%e 1 is missing, so S = {0,1};

%e 00 is missing, so S = {0,1,0,0};

%e 01 and 10 are now visible, but 11 is missing, so S = {0,1,0,0,1,1};

%e 000 is missing, so S = {0,1,0,0,1,1,0,0,0}; etc.

%p bString := proc(n,m) local a,i; a := [] ; for i from m-1 to 0 by -1 do a := [op(a), floor(n/2^i) mod 2] ; od: RETURN(a) ; end: A108736 := proc(nmax) local S,m,b,partoverl,overl,mbstr; S := [] ; m := 1: while nops(S) < nmax do for b from 0 to 2^m-1 do mbstr := bString(b,m) ; if verify(mbstr,S,'sublist') = false then partoverl := false ; for overl from m-1 to 1 by -1 do if verify(mbstr[1..overl],S[ -overl..-1],'sublist') = true then S := [op(S),op(mbstr[overl+1..nops(mbstr)])] ; partoverl := true ; break ; fi ; od; if partoverl = false then S := [op(S),op(mbstr)] ; fi ; fi ; od: m := m+1: od: RETURN(S) ; end: op(A108736(80)) ; # _R. J. Mathar_, Aug 15 2007

%o (Python)

%o from itertools import count, islice, product

%o def a(): # generator of terms

%o     S = ""

%o     for Sm in ("".join(w) for i in count(1) for w in product("01", repeat=i)):

%o         if Sm in S: continue

%o         for i in range(1, len(Sm)+1):

%o             v = Sm[-i:]

%o             t = "" if len(v) == len(Sm) else S[-len(Sm)+i:]

%o             if t+v == Sm: 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. A108737.

%K nonn,easy

%O 1,1

%A _N. J. A. Sloane_, Jun 23 2005

%E More terms from _R. J. Mathar_, Aug 15 2007