cp's OEIS Frontend

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

%I A076478 #57 Mar 17 2025 22:21:02
%S A076478 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,
%T A076478 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,
%U A076478 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
%N A076478 The binary Champernowne sequence: concatenate binary vectors of lengths 1, 2, 3, ... in numerical order.
%C A076478 Can also be seen as triangle where row n contains all binary vectors of length n+1. - _Reinhard Zumkeller_, Aug 18 2015
%C A076478 From _Clark Kimberling_, Jul 18 2021: (Start)
%C A076478 In the following list, W represents the sequence of words w(n) represented by A076478. The list includes five partitions and two self-inverse permutations of the positive integers.
%C A076478 length of w(n): A000523
%C A076478 positions in W of words w(n) such that # 0's = # 1's: A258410;
%C A076478 positions in W of words w(n) such that # 0's < # 1's: A346299;
%C A076478 positions in W of words w(n) such that # 0's > # 1's: A346300;
%C A076478 positions in W of words w(n) that end with 0: A005498;
%C A076478 positions in W of words w(n) that end with 1: A005843;
%C A076478 positions in W of words w(n) such that first digit = last digit: A346301;
%C A076478 positions in W of words w(n) such that first digit != last digit: A346302;
%C A076478 positions in W of words w(n) such that 1st digit = 0 and last digit 0: A171757;
%C A076478 positions in W of words w(n) such that 1st digit = 0 and last digit 1: A346303;
%C A076478 positions in W of words w(n) such that 1st digit = 1 and last digit 0: A346304;
%C A076478 positions in W of words w(n) such that 1st digit = 1 and last digit 1: A346305;
%C A076478 position in W of n-th positive integer (base 2):  A206332;
%C A076478 positions in W of binary complement of w(n):  A346306;
%C A076478 sum of digits in w(n): A048881;
%C A076478 number of runs in w(n): A346307;
%C A076478 positions in W of palindromes: A346308;
%C A076478 positions in W of words such that #0's - #1's is odd: A346309;
%C A076478 positions in W of words such that #0's - #1's is even: A346310;
%C A076478 positions in W of the reversal of the n-th word in W: A081241. (End)
%D A076478 Bodil Branner, Dynamics, Chap. IV.14 of The Princeton Companion to Mathematics, ed. T. Gowers, p. 499.
%D A076478 K. Dajani and C. Kraaikamp, Ergodic Theory of Numbers, Math. Assoc. America, 2002, p. 72.
%H A076478 Reinhard Zumkeller, <a href="/A076478/b076478.txt">Table of n, a(n) for n = 0..10000</a>
%H A076478 Michael Barnsley and Andrew Vince, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.124.10.905">Self-similar polygonal tiling</a>, The American Mathematical Monthly 124.10 (2017): 905-921. See page 917.
%H A076478 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%F A076478 To get the m-th binary vector, write m+1 in base 2 and remove the initial 1. - _Clark Kimberling_, Feb 07 2010
%e A076478 0,
%e A076478 1,
%e A076478 0,0,
%e A076478 0,1,
%e A076478 1,0,
%e A076478 1,1,
%e A076478 0,0,0,
%e A076478 0,0,1,
%e A076478 0,1,0,
%e A076478 0,1,1,
%e A076478 1,0,0,
%e A076478 1,0,1,
%e A076478 ...
%t A076478 d[n_] := Rest@IntegerDigits[n + 1, 2] + 1; -1 + Flatten[Array[d, 50]] (* _Clark Kimberling_, Feb 07 2012 *)
%t A076478 z = 1000;
%t A076478 t1 = Table[Tuples[{0, 1}, n], {n, 1, 10}];
%t A076478 "All binary words, lexicographic order:"
%t A076478 tt = Flatten[t1, 1]; (* all binary words, lexicographic order *)
%t A076478 "All binary words, flattened:"
%t A076478 Flatten[tt];
%t A076478 w[n_] := tt[[n]];
%t A076478 "List tt of all binary words:"
%t A076478 tt = Table[w[n], {n, 1, z}]; (*  all the binary words *)
%t A076478 u1 = Flatten[tt]; (* words, concatenated, A076478, binary Champernowne sequence *)
%t A076478 u2 = Map[Length, tt];
%t A076478 "Positions of 0^n:"
%t A076478 Flatten[Position[Map[Union, tt], {0}]]
%t A076478 "Positions of 1^n:"
%t A076478 Flatten[Position[Map[Union, tt], {1}]]
%t A076478 "Positions of words in which #0's = #1's:"  (* A258410 *)
%t A076478 "This and the next two sequences partition N."
%t A076478 u3 = Select[Range[Length[tt]], Count[tt[[#]], 0] == Count[tt[[#]], 1] &]
%t A076478 "Positions of words in which #0's < #1's:"  (* A346299 *)
%t A076478 u4 = Select[Range[Length[tt]], Count[tt[[#]], 0] < Count[tt[[#]], 1] &]
%t A076478 "Positions of words in which #0's > #1's:"  (* A346300 *)
%t A076478 u5 = Select[Range[Length[tt]], Count[tt[[#]], 0] > Count[tt[[#]], 1] &]
%t A076478 "Positions of words ending with 0:" (* A005498 *)
%t A076478 u6 = Select[Range[Length[tt]], Last[tt[[#]]] == 0 &]
%t A076478 "Positions of words ending with 1:" (* A005843 *)
%t A076478 u7 = Select[Range[Length[tt]], Last[tt[[#]]] == 1 &]
%t A076478 "Positions of words starting and ending with same digit:" (* A346301 *)
%t A076478 u8 = Select[Range[Length[tt]], First[tt[[#]]] == Last[tt[[#]]] &]
%t A076478 "Positions of words starting and ending with opposite digits:" (* A346302  *)
%t A076478 u9 = Select[Range[Length[tt]], First[tt[[#]]] != Last[tt[[#]]] &]
%t A076478 "Positions of words starting with 0 and ending with 0:" (* A346303 *)
%t A076478 "This and the next three sequences partition N."
%t A076478 u10 = Select[Range[Length[tt]], First[tt[[#]]] == 0 && Last[tt[[#]]] == 0 &]
%t A076478 "Positions of words starting with 0 and ending with 1:" (* A171757 *)
%t A076478 u11 = Select[Range[Length[tt]], First[tt[[#]]] == 0 && Last[tt[[#]]] == 1 &]
%t A076478 "Positions of words starting with 1 and ending with 0:" (* A346304 *)
%t A076478 u12 = Select[Range[Length[tt]], First[tt[[#]]] == 1 && Last[tt[[#]]] == 0 &]
%t A076478 "Positions of words starting with 1 and ending with 1:" (* A346305 *)
%t A076478 u13 = Select[Range[Length[tt]], First[tt[[#]]] == 1 && Last[tt[[#]]] == 1 &]
%t A076478 "Position of n-th positive integer (base 2) in tt:"
%t A076478 d[n_] := If[First[w[n]] == 1, FromDigits[w[n], 2]];
%t A076478 u14 = Flatten[Table[Position[Table[d[n], {n, 1, 200}], n], {n, 1, 200}]] (* A206332 *)
%t A076478 "Position of binary complement of w(n):"
%t A076478 u15 = comp = Flatten[Table[Position[tt, 1 - w[n]], {n, 1, 50}]] (* A346306 *)
%t A076478 "Sum of digits of w(n):"
%t A076478 u16 = Table[Total[w[n]], {n, 1, 100}] (* A048881 *)
%t A076478 "Number of runs in w(n):"
%t A076478 u17 = Map[Length, Table[Map[Length, Split[w[n]]], {n, 1, 100}]] (* A346307 *)
%t A076478 "Palindromes:"
%t A076478 Select[tt, # == Reverse[#] &]
%t A076478 "Positions of palindromes:"
%t A076478 u18 = Select[Range[Length[tt]], tt[[#]] == Reverse[tt[[#]]] &] (* A346308 *)
%t A076478 "Positions of words in which #0's - #1's is odd:"
%t A076478 u19 = Select[Range[Length[tt]], OddQ[Count[w[#], 0] - Count[w[#], 1]] &] (* A346309 *)
%t A076478 "Positions of words in which #0's - #1's is even:"
%t A076478 u20 = Select[Range[Length[tt]], EvenQ[Count[w[#], 0] - Count[w[#], 1]] &] (* A346310 *)
%t A076478 "Position of the reversal of the n-th word:"  (* A081241 *)
%t A076478 u21 = Flatten[Table[Position[tt, Reverse[w[n]]], {n, 1, 150}]]
%t A076478 (* _Clark Kimberling_, Jul 18 2011 *)
%o A076478 (PARI) {m=5; for(d=1,m, for(k=0,2^d-1,v=binary(k); while(matsize(v)[2]<d,v=concat(0,v)); for(j=1,matsize(v)[2],print1(v[j],","))))}
%o A076478 (PARI) listn(n)= my(a=List(), i=0, s=0); while(s<=n, listput(~a, binary(i++)[^1]); s+=#a[#a]); concat(a)[1..n+1]; \\ _Ruud H.G. van Tol_, Mar 17 2025
%o A076478 (Haskell)
%o A076478 import Data.List (unfoldr)
%o A076478 a076478 n = a076478_list !! n
%o A076478 a076478_list = concat $ tail $ map (tail . reverse . unfoldr
%o A076478    (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2 )) [1..]
%o A076478 -- _Reinhard Zumkeller_, Feb 08 2012
%o A076478 (Haskell)
%o A076478 a076478_row n = a076478_tabf !! n :: [[Int]]
%o A076478 a076478_tabf = tail $ iterate (\bs -> map (0 :) bs ++ map (1 :) bs) [[]]
%o A076478 a076478_list' = concat $ concat a076478_tabf
%o A076478 -- _Reinhard Zumkeller_, Aug 18 2015
%o A076478 (Python)
%o A076478 from itertools import count, product
%o A076478 def agen():
%o A076478     for digits in count(1):
%o A076478         for b in product([0, 1], repeat=digits):
%o A076478             yield from b
%o A076478 g = agen()
%o A076478 print([next(g) for n in range(105)]) # _Michael S. Branicky_, Jul 18 2021
%Y A076478 Cf. A007931, A030308, A053645.
%Y A076478 Cf. A341256, A341258, A341334, A342753, A342910.
%K A076478 nonn,easy,tabf
%O A076478 0,1
%A A076478 _N. J. A. Sloane_, Nov 10 2002
%E A076478 Extended by _Klaus Brockhaus_, Nov 11 2002