cp's OEIS Frontend

A362009 a(n) is the index of the first binary string which does not appear in the concatenation of the binary strings indexed by the preceding terms a(1..n-1).

%I A362009 #37 Apr 30 2023 20:54:05
%S A362009 1,2,3,6,7,12,14,15,25,28,31,34,35,38,45,62,67,72,76,78,80,83,90,91,
%T A362009 100,107,114,116,126,129,142,144,147,155,158,168,171,173,175,180,185,
%U A362009 198,205,226,228,250,257,260,262,266,272,274,279,290,294,296,310,313
%N A362009 a(n) is the index of the first binary string which does not appear in the concatenation of the binary strings indexed by the preceding terms a(1..n-1).
%C A362009 Binary strings are indexed starting from 1 and ordered by length, and lexicographically among equal length, so 0, 1, 00, 01, 10, 11, 000, ...
%C A362009 The strings indexed by this sequence can be concatenated to form a binary constant b = .010011000... (see A362240).
%C A362009 By construction every binary string is present at least once in the digits of b. It follows that b is an irrational number.
%C A362009 Are the frequencies of 0 and 1 equal in b?
%C A362009 Or more generally, do binary strings of the same length appear with the same frequency and if so, how does the frequency depend on the length?
%H A362009 Neal Gersh Tolunsky, <a href="/A362009/b362009.txt">Table of n, a(n) for n = 1..10000</a>
%e A362009 The sequence begins
%e A362009   n      = 1, 2,  3,  4,  5,  6,  7,   8, ...
%e A362009   a(n)   = 1, 2,  3,  6,  7, 12, 14,  15, ...
%e A362009   string = 0  1  00  11 000 101 111 0000  ...
%e A362009 At n=4, strings 01 and 10 have already appeared in the preceding concatenation "0 1 00", and 11 is the next which has not so that a(4) = 6.
%e A362009 Strings kept and skipped begin
%e A362009   0-1-00-(skip 01)-(skip 10)-11-000-(skip 001)...
%t A362009 lcad[1] := {{0}, {1}};
%t A362009 lcad[n_] :=
%t A362009   lcad[n] =
%t A362009    Join[Prepend[#, 0] & /@ lcad[n - 1],
%t A362009     Prepend[#, 1] & /@ lcad[n - 1]];  (* lcad[n] produces the list of binary strings of length n *)
%t A362009 nmx = 6; (* strings of length six or less *)
%t A362009 lsf = {}; nc0 = nc = 0;
%t A362009 Do[Do[++nc;
%t A362009   If[! MatchQ[lsf, List[___, Sequence @@ sc, ___]],
%t A362009    lsf = Join[lsf, sc]; Print[{++nc0, nc}]], {sc, lcad[n]}], {n, nmx}]
%t A362009 (* Prints the sequence in the form {n,a[n]} for n=1,2,...,29
%t A362009 this corresponds to strings of length six or less *)
%o A362009 (Python)
%o A362009 from itertools import count, islice, product
%o A362009 def agen(): # generator of terms
%o A362009     w, i = "", 0
%o A362009     for d in count(1):
%o A362009         for b in product("01", repeat=d):
%o A362009             b = "".join(b)
%o A362009             i += 1
%o A362009             if b not in w:
%o A362009                 yield i
%o A362009                 w += b
%o A362009 print(list(islice(agen(), 58))) # _Michael S. Branicky_, Apr 03 2023
%Y A362009 Cf. A362240, A362241, A118247.
%K A362009 nonn,base
%O A362009 1,2
%A A362009 _L. L. Salcedo_, Apr 03 2023