|
%I
%S 0,1,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,1,0,
%T 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,1,0,0,1,
%U 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,1,0,1,0,0,1,1
%N Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 0 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 Also called the Thue-Morse infinite word.
%C Fixed point of the morphism 0 --> 01, 1 --> 10, see example. [_Joerg Arndt_, Mar 12 2013]
%C The sequence is cube-free (does not contain three consecutive identical blocks) and is overlap-free (does not contain XYXYX where X is 0 or 1 and Y is any string of 0's and 1's).
%C a(n) = "parity sequence" = parity of number of 1's in binary representation of n.
%C To construct the sequence: alternate blocks of 0's and 1's of successive lengths A003159(k)-A003159(k-1), k=1,2,3,... (A003159(0)=0). Example: since the first seven differences of A003159 are 1,2,1,1,2,2,2, the sequence starts with 0,1,1,0,1,0,0,1,1,0,0. - _Emeric Deutsch_, Jan 10 2003
%C Characteristic function of A000069 (odious numbers). a(n) = 1-A010059(n) = A001285(n)-1. - Ralf Stephan, Jun 20 2003
%C a(n)=S2(n)mod 2, where S2(n) = sum of digits of n, n in base-2 notation. There is a class of generalized Thue-Morse sequences : Let Sk(n) = sum of digits of n; n in base-k notation. Let F(t) be some arithmetic function. Then a(n)= F(Sk(n)) mod m is a generalised Thue-Morse sequence. The classical Thue-Morse sequence is the case k=2, m=2, F(t)= 1. - Ctibor O. Zizka, Feb 12 2008
%C More generally, the partial sums of the generalized Thue-Morse sequences a(n)=F(Sk(n)) mod m are fractal, where Sk(n) is sum of digits of n, n in base k; F(t) is an arithmetic function; m integer. - Ctibor O. ZIZKA, Feb 25 2008
%C Starting with offset 1, = running sums mod 2 of the kneading sequence (A035263, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1,...); also parity of A005187: (1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19,...). - Gary W. Adamson, Jun 15 2008
%C Generalized Thue-Morse sequences mod n (n>1) = the array shown in A141803. As n -> Inf. the sequences -> (1, 2, 3,...). - Gary W. Adamson, Jul 10 2008
%C The Thue-Morse sequence for N = 3 = A053838, (sum of digits of n in base 3, mod 3): (0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2,...) = A004128 mod 3. [From Gary W. Adamson, Aug 24 2008]
%C For all positive integers k, the subsequence a(0) to a(2^k-1) is identical to the subsequence a(2^k+2^(k-1)) to a(2^(k+1)+2^(k-1)-1). That is to say, the first half of A_k is identical to the second half of B_k, and the second half of A_k is identical to the first quarter of B_{k+1}, which consists of the k/2 terms immediately following B_k.
%C Proof: The subsequence a(2^k+2^(k-1)) to a(2^(k+1)-1), the second half of B_k, is by definition formed from the subsequence a(2^(k-1)) to a(2^k-1), the second half of A_k, by interchanging its 0s and 1s. In turn, the subsequence a(2^(k-1)) to a(2^k-1), the second half of A_k, which is by definition also B_{k-1}, is by definition formed from the subsequence a(0) to a(2^(k-1)-1), the first half of A_k, which is by definition also A_{k-1}, by interchanging its 0s and 1s. Interchanging the 0s and 1s of a subsequence twice leaves it unchanged, so the subsequence a(2^k+2^(k-1)) to a(2^(k+1)-1), the second half of B_k, must be identical to the subsequence a(0) to a(2^(k-1)-1), the first half of A_k.
%C Also, the subsequence a(2^(k+1)) to a(2^(k+1)+2^(k-1)-1), the first quarter of B_{k+1}, is by definition formed from the subsequence a(0) to a(2^(k-1)-1), the first quarter of A_{k+1}, by interchanging its 0s and 1s. As noted above, the subsequence a(2^(k-1)) to a(2^k-1), the second half of A_k, which is by definition also B_{k-1}, is by definition formed from the subsequence a(0) to a(2^(k-1)-1), which is by definition A_{k-1}, by interchanging its 0s and 1s, as well. If two subsequences are formed from the same subsequence by interchanging its 0s and 1s then they must be identical, so the subsequence a(2^(k+1)) to a(2^(k+1)+2^(k-1)-1), the first quarter of B_{k+1}, must be identical to the subsequence a(2^(k-1)) to a(2^k-1), the second half of A_k.
%C Therefore the subsequence a(0),..., a(2^(k-1)-1), a(2^(k-1)),..., a(2^k-1) is identical to the subsequence a(2^k+2^(k-1)),..., a(2^(k+1)-1), a(2^(k+1)),..., a(2^(k+1)+2^(k-1)-1), QED.
%C According to the German chess rules of 1929 a game of chess was drawn if the same sequence of moves was repeated three times consecutively. Euwe, see the references, proved that this rule could lead to infinite games. For his proof he reinvented the Thue-Morse sequence. [From Johannes W. Meijer, Feb 04 2010.]
%C "Thue-Morse 0->01 & 1->10, at each stage append the previous with its complement. Start with 0,1,2,3 and write them in binary. Next calculate the sum of the digits (mod 2) - that is divide the sum by 2 and use the remainder." Pickover, The Math Book.
%C Let s_2(n) be the sum of the base-2 digits of n and epsilon(n) = (-1)^s_2(n), the Thue-Morse sequence, then prod(n>=0, ((2*n+1)/(2*n+2))^epsilon(n) ) = 1/sqrt(2). [_Jonathan Vos Post_, Jun 06 2012]
%D A. Aksenov, The Newman phenomenon and Lucas sequence, Arxiv preprint arXiv:1108.5352, 2011
%D J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 15.
%D Allouche, J.-P. and Cohen, H. "Dirichlet Series and Curious Infinite Products." Bull. London Math. Soc. 17, 531-538, 1985.
%D F. Axel et al., Vibrational modes in a one dimensional "quasi-alloy": the Morse case, J. de Physique, Colloq. C3, Supp. to No. 7, Vol. 47 (Jul 1986), pp. C3-181-C3-186; see Eq. (10).
%D J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
%D B. Bollobas, The Art of Mathematics: Coffee Time in Memphis, Cambridge, 2006, p. 224.
%D S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math., 24 (1989), 83-96. doi:10.1016/0166-218X(92)90274-E. - From _N. J. A. Sloane_, Jul 10 2012
%D Y. Bugeaud and M. Queffélec, On Rational Approximation of the Binary Thue-Morse-Mahler Number, Journal of Integer Sequences, 16 (2013), #13.2.3.
%D A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci. 63 (1989), 333-348. - From _N. J. A. Sloane_, Jul 10 2012
%D F. Dejean, Sur un theoreme de Thue. J. Combinatorial Theory Ser. A 13 (1972), 90-99.
%D Dekking, F. M. On repetitions of blocks in binary sequences. J. Combinatorial Theory Ser. A 20 (1976), no. 3, 292--299. MR0429728(55 #2739)
%D J. Endrullis, D. Hendriks and J. W. Klop. Degrees of streams, http://www.cs.vu.nl/~diem/publication/pdf/degrees.pdf
%D M. Euwe, Mengentheoretische Betrachtungen Ueber das Schachspiel, Proceedings Koninklijke Nederlandse Akademie van Wetenschappen, Amsterdam, Vol. 32 (5): 633-642, 1929. [From _Johannes W. Meijer_, Feb 04 2010.]
%D S. Ferenczi, Complexity of sequences and dynamical systems, Discrete Math., 206 (1999), 145-154.
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.8.
%D W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
%D J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
%D G. A. Hedlund, Remarks on the work of Axel Thue on sequences, Nordisk Mat. Tid., 15 (1967), 148-150.
%D A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149-159.
%D B. Kitchens, Review of "Computational Ergodic Theory" by G. H. Choe, Bull. Amer. Math. Soc., 44 (2007), 147-155.
%D Naoki Kobayashi, Kazutaka Matsuda and Ayumi Shinohara, Functional Programs as Compressed Data, http://www.kb.ecei.tohoku.ac.jp/~koba/papers/pepm2012-full.pdf
%D Le Breton, Xavier, Linear independence of automatic formal power series. Discrete Math. 306 (2006), no. 15, 1776-1780.
%D M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.
%D Mignosi, F.; Restivo, A.; Sciortino, M. Words and forbidden factors. WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096) - From _N. J. A. Sloane_, Jul 10 2012
%D M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22 (1921), 84-100.
%D K. Nakano, Shall We Juggle, Coinductively?, in Certified Programs and Proofs, Lecture Notes in Computer Science Volume 7679, 2012, pp 160-172, DOI 10.1007/978-3-642-35308-6_14. - From _N. J. A. Sloane_, Jan 02 2013
%D C. A. Pickover, Wonders of Numbers, Adventures in Mathematics, Mind and Meaning, Chapter 17, 'The Pipes of Papua,' Oxford University Press, Oxford, England, 2000, pages 34 - 38.
%D C. A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 60.
%D Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 316.
%D G. Richomme, K. Saari, L. Q. Zamboni, Abelian complexity in minimal subshifts, J. London Math. Soc. 83(1) (2011) 79-95.
%D Benoit Rittaud, Elise Janvresse, Emmanuel Lesigne and Jean-Christophe Novelli, Quand les maths se font discretes, Le Pommier, 2008 (ISBN 978-2-7465-0370-0).
%D A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.
%D Shallit, J. O. "On Infinite Products Associated with Sums of Digits." J. Number Th. 21, 128-134, 1985.
%D J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, Context-free coalgebras, 2013; http://oai.cwi.nl/oai/asset/21313/21313A.pdf
%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 890.
%H N. J. A. Sloane, <a href="/A010060/b010060.txt">Table of n, a(n) for n = 0..16383</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>, p.44
%H J.-P. Allouche, <a href="http://algo.inria.fr/seminars/sem92-93/allouche.ps">Series and infinite products related to binary expansions of integers</a>
%H J.-P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/Relative.ps">A sequence related to that of Thue-Morse</a>, Discrete Math., 139 (1995), 455-461.
%H J.-P. Allouche and M. Mendes France, <a href="http://www.lri.fr/~allouche/">Automata and Automatic Sequences.</a>
%H J.-P. Allouche and J. Shallit, <a href="http://www.lri.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>
%H 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 Ricardo Astudillo, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">On a Class of Thue-Morse Type Sequences</a>, J. Integer Seqs., Vol. 6, 2003.
%H Jean Berstel, <a href="http://www-igm.univ-mlv.fr/~berstel/">Home Page</a>
%H Bertazzon J.-F., <a href="http://arxiv.org/abs/1201.2502">Resolution of an integral equation with the Thue-Morse sequence</a>, arXiv:1201.2502v1 [math.CO], Jan 12, 2012.
%H E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/abs/math.CO/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, J. Num. Theory 117 (2006), 191-215.
%H A. S. Fraenkel, <a href="http://www.wisdom.weizmann.ac.il/~fraenkel/">Home Page</a>
%H A. S. Fraenkel, <a href="http://www.integers-ejcnt.org/">New games related to old and new sequences</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>
%H Daniel Goc, Luke Schaeffer and Jeffrey Shallit, <a href="http://arxiv.org/abs/1206.5352">The Subword Complexity of k-Automatic Sequences is k-Synchronized</a>, arXiv 1206.5352, Jun 28 2012.
%H Dimitri Hendriks, Frits G. W. Dannenberg, Jorg Endrullis, Mark Dow and Jan Willem Klop, <a href="http://arxiv.org/abs/1201.3786">Arithmetic Self-Similarity of Infinite Sequences</a>, Arxiv preprint 1201.3786, 2012.
%H A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 79. <a href="http://tohbook.info">Book's website</a>
%H M. Morse, <a href="http://links.jstor.org/sici?sici=0002-9947%28192101%2922%3A1%3C84%3ARGOASO%3E2.0.CO%3B2-9">Recurrent geodesics on a surface of negative curvature</a> (page images), Trans. Amer. Math. Soc., 22 (1921), 84-100.
%H C. A. Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," <a href="http://www.zentralblatt-math.org/zmath/en/search/?q=an:0983.00008&format=complete">Zentralblatt review</a>
%H N. J. A. Sloane, <a href="/A010060/a010060.txt">The first 1000 terms as a string</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Thue-MorseSequence.html">Thue-Morse Sequence</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Thue-MorseConstant.html">Thue-Morse Constant</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Parity.html">Parity</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>
%F a(2n)=a(n), a(2n+1)=1-a(n), a(0)=0. Also, a(k+2^m)=1-a(k) if 0<=k<2^m.
%F Let S(0) = 0 and for k >=1, construct S(k) from S(k-1) by mapping 0 -> 01 and 1 -> 10; sequence is S(infinity).
%F G.f.: (1/(1-x) - product_{k>=0} 1-x^(2^k))/2. - Benoit Cloitre, Apr 23 2003
%F a(0)=0, a(n)=(n+a(floor(n/2))) mod 2; also a(0)=0, a(n)=(n-a(floor(n/2))) mod 2 - Benoit Cloitre, Dec 10 2003
%F a(n)=-1+sum(k=0, n, binomial(n, k){mod 2}) {mod 3}=-1+A001316(n) {mod 3} - Benoit Cloitre, May 09 2004
%F Let b(1)=1 and b(n)=b(ceil(n/2))-b(floor(n/2)) then a(n-1)=(1/2)*(1-b(2n-1)) - Benoit Cloitre, Apr 26 2005
%F a(n) = A001969(n) - 2n. - Frank Adams-Watters, Aug 28 2006
%F a(n) = A115384(n) - A115384(n-1) for n>0. - _Reinhard Zumkeller_, Aug 26 2007
%F For n>=0, a(A004760(n+1))=1-a(n). [From Vladimir Shevelev, Apr 25 2009]
%F a(A160217(n))=1-a(n). [From Vladimir Shevelev, May 05 2009]
%F A010060(n) == A000069(n)(mod 2). - Robert G. Wilson v, Jan 18 2012.
%e The evolution starting at 0 is:
%e .0
%e .0, 1
%e .0, 1, 1, 0
%e .0, 1, 1, 0, 1, 0, 0, 1
%e .0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0
%e .0, 1, 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
%e .......
%e A_2 = 0 1 1 0, so B_2 = 1 0 0 1 and A_3 = A_2 B_2 = 0 1 1 0 1 0 0 1.
%e From _Joerg Arndt_, Mar 12 2013: (Start)
%e The first steps of the iterated substitution are
%e Start: 0
%e Rules:
%e 0 --> 01
%e 1 --> 10
%e -------------
%e 0: (#=1)
%e 0
%e 1: (#=2)
%e 01
%e 2: (#=4)
%e 0110
%e 3: (#=8)
%e 01101001
%e 4: (#=16)
%e 0110100110010110
%e 5: (#=32)
%e 01101001100101101001011001101001
%e 6: (#=64)
%e 0110100110010110100101100110100110010110011010010110100110010110
%e (End)
%p s := proc(k) local i, ans; ans := [ 0,1 ]; for i from 0 to k do ans := [ op(ans),op(map(n->(n+1) mod 2, ans)) ] od; RETURN(ans); end; t1 := s(6); A010060 := n->t1[n]; # s(k) gives first 2^(k+2) terms.
%p a := proc(k) b := [0]: for n from 1 to k do b := subs({0=[0,1], 1=[1,0]},b) od: b; end; # a(k), after the removal of the brackets, gives the first 2^k terms. # Example: a(3); gives [[[[0, 1], [1, 0]], [[1, 0], [0, 1]]]]
%p A010060:=proc(n) local n2: n2:=convert(n,base,2): sum(n2[j],j=1..nops(n2)) mod 2; end:
%p seq(A010060(n),n=0..104); # _Emeric Deutsch_, Mar 19 2005
%t Table[ If[ OddQ[ Count[ IntegerDigits[n, 2], 1]], 1, 0], {n, 0, 100}];
%t mt = 0; Do[ mt = ToString[mt] <> ToString[(10^(2^n) - 1)/9 - ToExpression[mt] ], {n, 0, 6} ]; Prepend[ RealDigits[ N[ ToExpression[mt], 2^7] ] [ [1] ], 0]
%t Mod[ Count[ #, 1 ]& /@Table[ IntegerDigits[ i, 2 ], {i, 0, 2^7 - 1} ], 2 ] (from Harlan J. Brothers, Feb 05 2005)
%t Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {0}, 7] (* Robert G. Wilson v Sep 26 2006 *)
%t a[n_] := If[n == 0, 0, If[Mod[n, 2] == 0, a[n/2], 1 - a[(n - 1)/2]]] [From Ben Branman, Oct 22 2010]
%o (Haskell)
%o a010060 n = a010060_list !! n
%o a010060_list =
%o 0 : interleave (complement a010060_list) (tail a010060_list)
%o where complement = map (1 - )
%o interleave (x:xs) ys = x : interleave ys xs
%o -- Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 29 2003
%o -- Edited by _Reinhard Zumkeller_, Oct 03 2012
%o (PARI) a(n)=if(n<1,0,sum(k=0,length(binary(n))-1,bittest(n,k))%2)
%o (PARI) a(n)=if(n<1,0,subst(Pol(binary(n)), x,1)%2)
%o (PARI) { default(realprecision, 6100); x=0.0; m=20080; for (n=1, m-1, x=x+x; x=x+sum(k=0, length(binary(n))-1, bittest(n, k))%2); x=2*x/2^m; for (n=0, 20000, d=floor(x); x=(x-d)*2; write("b010060.txt", n, " ", d)); } [From _Harry J. Smith_, Apr 28 2009]
%o (PARI) a(n)=hammingweight(n)%2 \\ _Charles R Greathouse IV_, Mar 22 2013
%Y Cf. A001285 (for 1, 2 version), A010059 (1, 0 version), A048707. A010060(n)=A000120(n) mod 2.
%Y Cf. A007413, A080813, A080814, A036581, A108694. See also the Thue (or Roth) constant A014578.
%Y Cf. also A001969, A035263, A005187, A115384, A132680, A141803, A104248.
%Y Backward first differences give A029883.
%Y Cf. A004128, A053838, A059448, A171900, A161916, A214212, A005942 (subword complexity), A010693 (Abelian complexity), A225186 (squares).
%K nonn,core,easy,nice,changed
%O 0,1
%A _N. J. A. Sloane_.
%E Additional comments from _Robert G. Wilson v_, Dec 29 2000
|
