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

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

Offset

1,1

Links

Michael S. Branicky, Table of n, a(n) for n = 1..10001

Example

We construct S as follows, starting with S = {}.
0 is missing, so S = {0};
1 is missing, so S = {0,1};
00 is missing, so S = {0,1,0,0};
01 and 10 are now visible, but 11 is missing, so S = {0,1,0,0,1,1};
000 is missing, so S = {0,1,0,0,1,1,0,0,0}; etc.

Maple

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

Prog

(Python)
from itertools import count, islice, product
def a(): # generator of terms
    S = ""
    for Sm in ("".join(w) for i in count(1) for w in product("01", repeat=i)):
        if Sm in S: continue
        for i in range(1, len(Sm)+1):
            v = Sm[-i:]
            t = "" if len(v) == len(Sm) else S[-len(Sm)+i:]
            if t+v == Sm: break
        S += v
        yield from list(map(int, v))
print(list(islice(a(), 105))) # Michael S. Branicky, Oct 27 2023

Crossrefs

Cf. A108737.

Sequence in context: A071986 A079944 A059652 * A362240 A079813 A078580

Adjacent sequences: A108733 A108734 A108735 * A108737 A108738 A108739

Keyword

nonn,easy

Author

N. J. A. Sloane, Jun 23 2005

Extensions

More terms from R. J. Mathar, Aug 15 2007

Status

approved