

A076478


The binary Champernowne sequence: concatenate binary vectors of lengths 1, 2, 3, ... in numerical order.


17



0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

Can also be seen as triangle where row n contains all binary vectors of length n+1.  Reinhard Zumkeller, Aug 18 2015
From Clark Kimberling, Jul 18 2021: (Start)
In the following list, W represents the sequence of words w(n) represented by A076478. The list includes five partitions and two selfinverse permutations of the positive integers.
length of w(n): A000523
positions in W of words w(n) such that # 0's = # 1's: A258410;
positions in W of words w(n) such that # 0's < # 1's: A346299;
positions in W of words w(n) such that # 0's > # 1's: A346300;
positions in W of words w(n) that end with 0: A005498;
positions in W of words w(n) that end with 1: A005843;
positions in W of words w(n) such that first digit = last digit: A346301;
positions in W of words w(n) such that first digit != last digit: A346302;
positions in W of words w(n) such that 1st digit = 0 and last digit 0: A171757;
positions in W of words w(n) such that 1st digit = 0 and last digit 1: A346303;
positions in W of words w(n) such that 1st digit = 1 and last digit 0: A346304;
positions in W of words w(n) such that 1st digit = 1 and last digit 1: A346305;
position in W of nth positive integer (base 2): A206332;
positions in W of binary complement of w(n): A346306;
sum of digits in w(n): A048881;
number of runs in w(n): A346307;
positions in W of palindromes: A346308;
positions in W of words such that #0's  #1's is odd: A346309;
positions in W of words such that #0's  #1's is even: A346310;
positions in W of the reversal of the nth word in W: A081241. (End)


REFERENCES

Bodil Branner, Dynamics, Chap. IV.14 of The Princeton Companion to Mathematics, ed. T. Gowers, p. 499.
K. Dajani and C. Kraaikamp, Ergodic Theory of Numbers, Math. Assoc. America, 2002, p. 72.


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Michael Barnsley and Andrew Vince, Selfsimilar polygonal tiling, The American Mathematical Monthly 124.10 (2017): 905921. See page 917.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.


FORMULA

To get the mth binary vector, write m+1 in base 2 and remove the initial 1.  Clark Kimberling, Feb 07 2010


EXAMPLE

0,
1,
0,0,
0,1,
1,0,
1,1,
0,0,0,
0,0,1,
0,1,0,
0,1,1,
1,0,0,
1,0,1,
...


MATHEMATICA

d[n_] := Rest@IntegerDigits[n + 1, 2] + 1; 1 + Flatten[Array[d, 50]] (* Clark Kimberling, Feb 07 2012 *)
z = 1000;
t1 = Table[Tuples[{0, 1}, n], {n, 1, 10}];
"All binary words, lexicographic order:"
tt = Flatten[t1, 1]; (* all binary words, lexicographic order *)
"All binary words, flattened:"
Flatten[tt];
w[n_] := tt[[n]];
"List tt of all binary words:"
tt = Table[w[n], {n, 1, z}]; (* all the binary words *)
u1 = Flatten[tt]; (* words, concatenated, A076478, binary Champernowne sequence *)
u2 = Map[Length, tt];
"Positions of 0^n:"
Flatten[Position[Map[Union, tt], {0}]]
"Positions of 1^n:"
Flatten[Position[Map[Union, tt], {1}]]
"Positions of words in which #0's = #1's:" (* A258410 *)
"This and the next two sequences partition N."
u3 = Select[Range[Length[tt]], Count[tt[[#]], 0] == Count[tt[[#]], 1] &]
"Positions of words in which #0's < #1's:" (* A346299 *)
u4 = Select[Range[Length[tt]], Count[tt[[#]], 0] < Count[tt[[#]], 1] &]
"Positions of words in which #0's > #1's:" (* A346300 *)
u5 = Select[Range[Length[tt]], Count[tt[[#]], 0] > Count[tt[[#]], 1] &]
"Positions of words ending with 0:" (* A005498 *)
u6 = Select[Range[Length[tt]], Last[tt[[#]]] == 0 &]
"Positions of words ending with 1:" (* A005843 *)
u7 = Select[Range[Length[tt]], Last[tt[[#]]] == 1 &]
"Positions of words starting and ending with same digit:" (* A346301 *)
u8 = Select[Range[Length[tt]], First[tt[[#]]] == Last[tt[[#]]] &]
"Positions of words starting and ending with opposite digits:" (* A346302 *)
u9 = Select[Range[Length[tt]], First[tt[[#]]] != Last[tt[[#]]] &]
"Positions of words starting with 0 and ending with 0:" (* A346303 *)
"This and the next three sequences partition N."
u10 = Select[Range[Length[tt]], First[tt[[#]]] == 0 && Last[tt[[#]]] == 0 &]
"Positions of words starting with 0 and ending with 1:" (* A171757 *)
u11 = Select[Range[Length[tt]], First[tt[[#]]] == 0 && Last[tt[[#]]] == 1 &]
"Positions of words starting with 1 and ending with 0:" (* A346304 *)
u12 = Select[Range[Length[tt]], First[tt[[#]]] == 1 && Last[tt[[#]]] == 0 &]
"Positions of words starting with 1 and ending with 1:" (* A346305 *)
u13 = Select[Range[Length[tt]], First[tt[[#]]] == 1 && Last[tt[[#]]] == 1 &]
"Position of nth positive integer (base 2) in tt:"
d[n_] := If[First[w[n]] == 1, FromDigits[w[n], 2]];
u14 = Flatten[Table[Position[Table[d[n], {n, 1, 200}], n], {n, 1, 200}]] (* A206332 *)
"Position of binary complement of w(n):"
u15 = comp = Flatten[Table[Position[tt, 1  w[n]], {n, 1, 50}]] (* A346306 *)
"Sum of digits of w(n):"
u16 = Table[Total[w[n]], {n, 1, 100}] (* A048881 *)
"Number of runs in w(n):"
u17 = Map[Length, Table[Map[Length, Split[w[n]]], {n, 1, 100}]] (* A346307 *)
"Palindromes:"
Select[tt, # == Reverse[#] &]
"Positions of palindromes:"
u18 = Select[Range[Length[tt]], tt[[#]] == Reverse[tt[[#]]] &] (* A346308 *)
"Positions of words in which #0's  #1's is odd:"
u19 = Select[Range[Length[tt]], OddQ[Count[w[#], 0]  Count[w[#], 1]] &] (* A346309 *)
"Positions of words in which #0's  #1's is even:"
u20 = Select[Range[Length[tt]], EvenQ[Count[w[#], 0]  Count[w[#], 1]] &] (* A346310 *)
"Position of the reversal of the nth word:" (* A081241 *)
u21 = Flatten[Table[Position[tt, Reverse[w[n]]], {n, 1, 150}]]
(* Clark Kimberling, Jul 18 2011 *)


PROG

(PARI) {m=5; for(d=1, m, for(k=0, 2^d1, v=binary(k); while(matsize(v)[2]<d, v=concat(0, v)); for(j=1, matsize(v)[2], print1(v[j], ", "))))}
(Haskell)
import Data.List (unfoldr)
a076478 n = a076478_list !! n
a076478_list = concat $ tail $ map (tail . reverse . unfoldr
(\x > if x == 0 then Nothing else Just $ swap $ divMod x 2 )) [1..]
 Reinhard Zumkeller, Feb 08 2012
(Haskell)
a076478_row n = a076478_tabf !! n :: [[Int]]
a076478_tabf = tail $ iterate (\bs > map (0 :) bs ++ map (1 :) bs) [[]]
a076478_list' = concat $ concat a076478_tabf
 Reinhard Zumkeller, Aug 18 2015
(Python)
from itertools import count, product
def agen():
for digits in count(1):
for b in product([0, 1], repeat=digits):
yield from b
g = agen()
print([next(g) for n in range(105)]) # Michael S. Branicky, Jul 18 2021


CROSSREFS

Cf. A007931, A030308, A053645.
Cf. A341256, A341258, A341334, A342753, A342910.
Sequence in context: A188294 A079101 A334941 * A091444 A091447 A106701
Adjacent sequences: A076475 A076476 A076477 * A076479 A076480 A076481


KEYWORD

nonn,easy,tabf,changed


AUTHOR

N. J. A. Sloane, Nov 10 2002


EXTENSIONS

Extended by Klaus Brockhaus, Nov 11 2002


STATUS

approved



