login
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).
3
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,2
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?
LINKS
EXAMPLE
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)...
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,base
AUTHOR
L. L. Salcedo, Apr 03 2023
STATUS
approved