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

1, 2, 3, 6, 7, 12, 14, 15, 25, 28, 31, 34, 35, 38, 45, 62, 67, 72, 76, 78, 80, 83, 90, 91, 100, 107, 114, 116, 126, 129, 142, 144, 147, 155, 158, 168, 171, 173, 175, 180, 185, 198, 205, 226, 228, 250, 257, 260, 262, 266, 272, 274, 279, 290, 294, 296, 310, 313

Offset: 1

Author

L. L. Salcedo, Apr 03 2023

Keywords

• nonn
• base

Comments

Binary strings are indexed starting from 1 and ordered by length, and lexicographically among equal length, so 0, 1, 00, 01, 10, 11, 000, ...

The strings indexed by this sequence can be concatenated to form a binary constant b = .010011000... (see A362240).

By construction every binary string is present at least once in the digits of b. It follows that b is an irrational number.

Are the frequencies of 0 and 1 equal in b?

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?

Examples

			The sequence begins
  n      = 1, 2,  3,  4,  5,  6,  7,   8, ...
  a(n)   = 1, 2,  3,  6,  7, 12, 14,  15, ...
  string = 0  1  00  11 000 101 111 0000  ...
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.
Strings kept and skipped begin
  0-1-00-(skip 01)-(skip 10)-11-000-(skip 001)...
		

Links

• Neal Gersh Tolunsky, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A362240, A362241, A118247.

Programs

Mathematica

lcad[1] := {{0}, {1}};
lcad[n_] :=
  lcad[n] =
   Join[Prepend[#, 0] & /@ lcad[n - 1],
    Prepend[#, 1] & /@ lcad[n - 1]];  (* lcad[n] produces the list of binary strings of length n *)
nmx = 6; (* strings of length six or less *)
lsf = {}; nc0 = nc = 0;
Do[Do[++nc;
  If[! MatchQ[lsf, List[_, Sequence @@ sc, _]],
   lsf = Join[lsf, sc]; Print[{++nc0, nc}]], {sc, lcad[n]}], {n, nmx}]
(* Prints the sequence in the form {n,a[n]} for n=1,2,...,29
this corresponds to strings of length six or less *)

Python

from itertools import count, islice, product
def agen(): # generator of terms
    w, i = "", 0
    for d in count(1):
        for b in product("01", repeat=d):
            b = "".join(b)
            i += 1
            if b not in w:
                yield i
                w += b
print(list(islice(agen(), 58))) # Michael S. Branicky, Apr 03 2023