cp's OEIS Frontend

A010059 Another version of the Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 1 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0's and 1's.

%I A010059 #122 Oct 25 2024 10:37:37
%S A010059 1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,
%T A010059 1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,
%U A010059 1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0
%N A010059 Another version of the Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 1 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0's and 1's.
%C A010059 Characteristic function of A001969 (evil numbers). - _Ralf Stephan_, Jun 20 2003
%C A010059 From _Gary W. Adamson_, Aug 24 2008: (Start)
%C A010059 Parity of A143579 (Odious numbers (A000069) interleaved with Evil numbers (A001969)).
%C A010059 Two conjectures: If n is even, the ratio of 1's to 0's = 1:1.
%C A010059 There are no three adjacent terms of the same parity. (End)
%C A010059 Conjecture (verified for the first 280000 entries): this is the characteristic function of A001969. - _R. J. Mathar_, Sep 05 2008
%C A010059 From _Michel Dekking_, Jan 05 2021: (Start)
%C A010059 Proof of these three conjectures: the first two follow directly from the third, because the sequence A010059 is the binary complement of the Thue-Morse sequence A010060.
%C A010059 For the third conjecture: the odious and evil numbers occur as quadruples EOOE and OEEO, simply by their definition. To obtain the mod 2 version of the interleave of the odious and evil numbers we therefore have to apply a transformation
%C A010059       EOOE -> OEOE, OEEO -> OEOE to these quadruples.
%C A010059 But this changes the parities from the corresponding 4n, 4n+1, 4n+2, 4n+3 quadruples from 0101 to 1001 in the first case, and from 0101 to 0110 in the second case. Since the quadruples EOOE and OEEO occur in a Thue Morse pattern, then also the quadruples 1001 and 0110 occur in a Thue Morse pattern, finishing the proof.
%C A010059 (End)
%D A010059 W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
%D A010059 M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.
%D A010059 A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.
%H A010059 Robert Israel, <a href="/A010059/b010059.txt">Table of n, a(n) for n = 0..10000</a>
%H A010059 J.-P. Allouche and Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps">The Ubiquitous Prouhet-Thue-Morse Sequence</a>, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
%H A010059 Scott Balchin and Dan Rust, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Rust/rust3.html">Computations for Symbolic Substitutions</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H A010059 Françoise Dejean, <a href="http://dx.doi.org/10.1016/0097-3165(72)90011-8">Sur un Théorème de Thue</a>, J. Combinatorial Theory, vol. 13 A, iss. 1 (1972) 90-99.
%H A010059 F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.pdf">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H A010059 Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>
%H A010059 G. A. Hedlund, <a href="https://www.jstor.org/stable/24525014">Remarks on the work of Axel Thue on sequences</a>, Nordisk Mat. Tid., 15 (1967), 148-150.
%H A010059 Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.
%H A010059 H. M. Morse, <a href="http://dx.doi.org/10.1090/S0002-9947-1921-1501161-8">Recurrent geodesics on a surface of negative curvature</a>, Trans. Amer. Math. Soc., 22 (1921), 84-100.
%H A010059 Stephen Wolfram, <a href="http://www.wolframscience.com/nksonline/page-889c-text?firstview=1">A New Kind Of Science | Online</a>.
%H A010059 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A010059 <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>
%F A010059 G.f.: (1/2) * (1/(1-x) + Product_{k>=0} (1 - x^2^k)). - _Ralf Stephan_, Jun 20 2003
%F A010059 a(n) = A143579(n) mod 2. - _Gary W. Adamson_, Aug 24 2008
%F A010059 a(n) + A010060(n) = 1 for all n.
%F A010059 a(n) = A159481(n+1) - A159481(n). - _Reinhard Zumkeller_, Apr 16 2009
%F A010059 a(n) + A026147(n-1) = 2n for n >= 1. - _Clark Kimberling_, Oct 06 2014
%F A010059 a(n) = A000069(n+1) (mod 2). - _John M. Campbell_, Jun 30 2016
%F A010059 a(n) = A059448(A054429(n)) = (A106400(n)+1)/2 = (1+A008836(A005940(1+n)))/2. - _Antti Karttunen_, May 30 2017
%F A010059 If A(n)=(a(0),a(2),...,a(2^n-1)), then A(n+1)=(A(n),1-A(n)). - _Arie Bos_, Jul 27 2022
%F A010059 a(n) = (1 + (-1)^A000120(n))/2. - _Lorenzo Sauras Altuzarra_, Mar 10 2024
%e A010059 The evolution starting at 1 is:
%e A010059 .1
%e A010059 .1, 0
%e A010059 .1, 0, 0, 1,
%e A010059 .1, 0, 0, 1, 0, 1, 1, 0
%e A010059 .1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1
%e A010059 .1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0
%e A010059 ...........
%p A010059 A010059 := n->1-A010060(n);
%p A010059 map(t->49-t,convert(StringTools[ThueMorse](1000),bytes)); # _Robert Israel_, Feb 02 2016
%p A010059 # second Maple program:
%p A010059 a := n -> ifelse(type(add(convert(n, base, 2)), even), 1, 0):
%p A010059 seq(a(n), n = 0 .. 104); # _Peter Luschny_, Mar 11 2024
%t A010059 Mod[ CoefficientList[Series[(1 + Sqrt[(1 - 3x)/(1 + x)])/(2(1 + x)), {x, 0, 111}], x], 2] (* Stephan Wolfram *)
%t A010059 CoefficientList[ Series[1/(1 - x) + Product[1 - x^2^k, {k, 0, 10}], {x, 0, 111}]/2, x] (* _Robert G. Wilson v_, Jul 16 2004 *)
%t A010059 Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {1}, 7] (* _Robert G. Wilson v_ Sep 26 2006 *)
%t A010059 od = Select[ Range[0, 129], OddQ@ DigitCount[ #, 2, 1] &]; ev = Select[ Range[0, 129], EvenQ@ DigitCount[ #, 2, 1] &]; Mod[ Flatten@ Transpose[{od, ev}], 2] (* _Robert G. Wilson v_, Apr 14 2009 *)
%t A010059 Nest[ Join[ #, Mod[2# + 1, 3]] &, {1}, 7] (* _Robert G. Wilson v_, Jul 27 2014 *)
%t A010059 {{1}}~Join~SubstitutionSystem[{0 -> {0, 1}, 1 -> {1, 0}}, {0}, 6] // Flatten (* _Michael De Vlieger_, Aug 15 2016, Version 10.2 *)
%t A010059 1 - ThueMorse[Range[0, 100]] (* _Paolo Xausa_, Oct 25 2024 *)
%o A010059 (Haskell) a010059 = (1 -) . a010060  -- _Reinhard Zumkeller_, Feb 04 2013
%o A010059 (PARI) a(n)=!(hammingweight(n)%2); \\ _Charles R Greathouse IV_, Mar 29 2013
%o A010059 (R)
%o A010059 maxrow <- 8 # by choice
%o A010059 b01 <- 0
%o A010059 for(m in 0:maxrow) for(k in 0:(2^m-1)){
%o A010059 b01[2^(m+1)+    k] <-   b01[2^m+k]
%o A010059 b01[2^(m+1)+2^m+k] <- 1-b01[2^m+k]
%o A010059 }
%o A010059 (b01 <- c(1,b01))
%o A010059 # _Yosu Yurramendi_, Apr 10 2017
%o A010059 (Python)
%o A010059 def A010059(n): return n.bit_count()&1^1 # _Chai Wah Wu_, Mar 01 2023
%Y A010059 Cf. A001285 (1, 2 version), A010060 (0, 1 version), A106400 (+1, -1 version), A059448 (with reversed subsections).
%Y A010059 Cf. also A000069, A026147, A159481.
%Y A010059 Cf. A000120, A001969, A143579.
%K A010059 nonn,easy
%O A010059 0,1
%A A010059 _N. J. A. Sloane_