A108736 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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