%I A007061 M0075
%S A007061 1,2,1,1,2,2,1,2,1,2,2,2,1,1,1,2,1,1,1,1,2,2,2,2,1,2,2,1,1,2,1,2,1,1,2,
%T A007061 1,1,2,2,2,1,2,1,1,1,2,2,1,1,1,1,1,2,1,2,2,1,2,2,2,2,2,1,1,2,2,1,1,2,2,
%U A007061 2,2,2,2,1,2,1,2,1,2,2,1,1,1,2,2,2,1,1,2,1,1,1,2,1,2,1,2,1,1,1,1,1,1,2
%N A007061 A maximally unpredictable sequence.
%C A007061 Klaus Sutner remarks (Jun 26 2006) that this sequence is very similar 
               to the Kimberling sequence A079101. Both sequences have every finite 
               binary word as a factor; in fact, essentially the same proof works 
               for both sequences.
%C A007061 Sutner continues: All words of length k seem to appear in the first 2^{k+2} 
               bits. This is true for the first billion bits of the sequence, but 
               no proof is known. The main open problem is whether the limiting 
               density of 0's is 1/2. It seems to require a large amount of effort 
               just to show that it is bounded away from 0, never mind some of the 
               more exotic properties of the sequence (see the Sutner reference).
%C A007061 Start with a single bit 0. If the first n bits U(n) = a(1)a(2)...a(n) 
               have already been chosen, let v be the longest suffix of U(n) that 
               already appears in U(n-1). Find the last occurrence of v in U(n-1) 
               and let b the bit that occurs immediately after. Then a(n+1) is the 
               complement of b. (The entry gives the bits as 1's and 2s instead 
               of 0's and 1's - compare A038219) - Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), 
               Aug 11 2006
%D A007061 A. Ehrenfeucht and J. Mycielski, A pseudorandom sequence - how random 
               is it?, Amer. Math. Monthly, 99 (1992), 373-375.
%D A007061 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A007061 Joshua Zucker, <a href="b007061.txt">Table of n, a(n) for n = 1..1999</
               a>
%H A007061 K. Sutner, <a href="http://www.cs.cmu.edu/~sutner/papers/em-sequence.ps.gz">
               The Ehrenfeucht-Mycielski sequence</a>
%Y A007061 Cf. A038219 (0-1 version), A079101.
%Y A007061 Sequence in context: A106495 A100428 A093914 this_sequence A001817 A091954 
               A080236
%Y A007061 Adjacent sequences: A007058 A007059 A007060 this_sequence A007062 A007063 
               A007064
%K A007061 nonn
%O A007061 1,2
%A A007061 N. J. A. Sloane (njas(AT)research.att.com), Mira Bernstein (mira(AT)math.berkeley.edu)
%E A007061 More terms from Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), 
               Aug 11 2006
%E A007061 Offset changed from 0 to 1, Aug 18 2006