This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A010060 #559 Jun 05 2025 10:04:16
%S A010060 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 A010060 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 A010060 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 A010060 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 A010060 Named after Axel Thue, whose name is pronounced as if it were spelled "Tü" where the ü sound is roughly as in the German word üben. (It is incorrect to say "Too-ee" or "Too-eh".) - _N. J. A. Sloane_, Jun 12 2018
%C A010060 Also called the Thue-Morse infinite word, or the Morse-Hedlund sequence, or the parity sequence.
%C A010060 Fixed point of the morphism 0 --> 01, 1 --> 10, see example. - _Joerg Arndt_, Mar 12 2013
%C A010060 The sequence is cubefree (does not contain three consecutive identical blocks) [see Offner for a direct proof] 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 A010060 a(n) = "parity sequence" = parity of number of 1's in binary representation of n.
%C A010060 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 A010060 Characteristic function of A000069 (odious numbers). - _Ralf Stephan_, Jun 20 2003
%C A010060 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 generalized Thue-Morse sequence. The classical Thue-Morse sequence is the case k=2, m=2, F(t)= 1*t. - _Ctibor O. Zizka_, Feb 12 2008 (with correction from _Daniel Hug_, May 19 2017)
%C A010060 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 A010060 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 A010060 Generalized Thue-Morse sequences mod n (n>1) = the array shown in A141803. As n -> infinity the sequences -> (1, 2, 3, ...). - _Gary W. Adamson_, Jul 10 2008
%C A010060 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. - _Gary W. Adamson_, Aug 24 2008
%C A010060 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 A010060 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 0's and 1's. 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 0's and 1's. Interchanging the 0's and 1's 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 A010060 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 0's and 1's. 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 0's and 1's, as well. If two subsequences are formed from the same subsequence by interchanging its 0's and 1's 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 A010060 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 A010060 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. - _Johannes W. Meijer_, Feb 04 2010
%C A010060 "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 A010060 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
%C A010060 Dekking shows that the constant obtained by interpreting this sequence as a binary expansion is transcendental; see also "The Ubiquitous Prouhet-Thue-Morse Sequence". - _Charles R Greathouse IV_, Jul 23 2013
%C A010060 Drmota, Mauduit, and Rivat proved that the subsequence a(n^2) is normal--see A228039. - _Jonathan Sondow_, Sep 03 2013
%C A010060 Although the probability of a 0 or 1 is equal, guesses predicated on the latest bit seen produce a correct match 2 out of 3 times. - _Bill McEachen_, Mar 13 2015
%C A010060 From a(0) to a(2n+1), there are n+1 terms equal to 0 and n+1 terms equal to 1 (see Hassan Tarfaoui link, Concours Général 1990). - _Bernard Schott_, Jan 21 2022
%D A010060 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 15.
%D A010060 Jason Bell, Michael Coons, and Eric Rowland, "The Rational-Transcendental Dichotomy of Mahler Functions", Journal of Integer Sequences, Vol. 16 (2013), #13.2.10.
%D A010060 J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
%D A010060 B. Bollobas, The Art of Mathematics: Coffee Time in Memphis, Cambridge, 2006, p. 224.
%D A010060 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.
%D A010060 Yann Bugeaud and Guo-Niu Han, A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence, Electronic Journal of Combinatorics 21(3) (2014), #P3.26.
%D A010060 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 A010060 Currie, James D. "Non-repetitive words: Ages and essences." Combinatorica 16.1 (1996): 19-40
%D A010060 Colin Defant, Anti-Power Prefixes of the Thue-Morse Word, Journal of Combinatorics, 24(1) (2017), #P1.32
%D A010060 F. M. Dekking, Transcendance du nombre de Thue-Morse, Comptes Rendus de l'Academie des Sciences de Paris 285 (1977), pp. 157-160.
%D A010060 F. M. Dekking, On repetitions of blocks in binary sequences. J. Combinatorial Theory Ser. A 20 (1976), no. 3, pp. 292-299. MR0429728(55 #2739)
%D A010060 Dekking, Michel, Michel Mendès France, and Alf van der Poorten. "Folds." The Mathematical Intelligencer, 4.3 (1982): 130-138 & front cover, and 4:4 (1982): 173-181 (printed in two parts).
%D A010060 Dubickas, Artūras. On a sequence related to that of Thue-Morse and its applications. Discrete Math. 307 (2007), no. 9-10, 1082--1093. MR2292537 (2008b:11086).
%D A010060 Fabien Durand, Julien Leroy, and Gwenaël Richomme, "Do the Properties of an S-adic Representation Determine Factor Complexity?", Journal of Integer Sequences, Vol. 16 (2013), #13.2.6.
%D A010060 M. Euwe, Mengentheoretische Betrachtungen Über das Schachspiel, Proceedings Koninklijke Nederlandse Akademie van Wetenschappen, Amsterdam, Vol. 32 (5): 633-642, 1929.
%D A010060 S. Ferenczi, Complexity of sequences and dynamical systems, Discrete Math., 206 (1999), 145-154.
%D A010060 S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.8.
%D A010060 W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
%D A010060 J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
%D A010060 A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149-159.
%D A010060 Mari Huova and Juhani Karhumäki, "On Unavoidability of k-abelian Squares in Pure Morphic Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.9.
%D A010060 B. Kitchens, Review of "Computational Ergodic Theory" by G. H. Choe, Bull. Amer. Math. Soc., 44 (2007), 147-155.
%D A010060 Le Breton, Xavier, Linear independence of automatic formal power series. Discrete Math. 306 (2006), no. 15, 1776-1780.
%D A010060 M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.
%D A010060 Donald MacMurray, A mathematician gives an hour to chess, Chess Review 6 (No. 10, 1938), 238. [Discusses Marston's 1938 article]
%D A010060 Mauduit, Christian. Multiplicative properties of the Thue-Morse sequence. Period. Math. Hungar. 43 (2001), no. 1-2, 137--153. MR1830572 (2002i:11081)
%D A010060 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 A010060 C. A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 60.
%D A010060 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 A010060 Narad Rampersad and Elise Vaslet, "On Highly Repetitive and Power Free Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.7.
%D A010060 G. Richomme, K. Saari, L. Q. Zamboni, Abelian complexity in minimal subshifts, J. London Math. Soc. 83(1) (2011) 79-95.
%D A010060 Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%D A010060 M. Rigo, P. Salimov, and E. Vandomme, "Some Properties of Abelian Return Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
%D A010060 Benoit Rittaud, Elise Janvresse, Emmanuel Lesigne and Jean-Christophe Novelli, Quand les maths se font discrètes, Le Pommier, 2008 (ISBN 978-2-7465-0370-0).
%D A010060 A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.
%D A010060 Shallit, J. O. "On Infinite Products Associated with Sums of Digits." J. Number Th. 21, 128-134, 1985.
%D A010060 Ian Stewart, "Feedback", Mathematical Recreations Column, Scientific American, 274 (No. 3, 1996), page 109 [Historical notes on this sequence]
%D A010060 Thomas Stoll, On digital blocks of polynomial values and extractions in the Rudin-Shapiro sequence, RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2016, 50, pp. 93-99. <hal-01278708>.
%D A010060 A. Thue. Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, No. 7 (1906), 1-22.
%D A010060 A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 1 (1912), 1-67.
%D A010060 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 890.
%H A010060 N. J. A. Sloane, <a href="/A010060/b010060.txt">Table of n, a(n) for n = 0..16383</a>
%H A010060 A. G. M. Ahmed, <a href="http://archive.bridgesmathart.org/2013/bridges2013-263.pdf">AA Weaving</a>. In: Proceedings of Bridges 2013: Mathematics, Music, Art, ..., 2013.
%H A010060 A. Aksenov, <a href="http://arxiv.org/abs/1108.5352">The Newman phenomenon and Lucas sequence</a>, arXiv preprint arXiv:1108.5352 [math.NT], 2011-2012.
%H A010060 Max A. Alekseyev and N. J. A. Sloane, <a href="https://arxiv.org/abs/2112.14365">On Kaprekar's Junction Numbers</a>, arXiv:2112.14365, 2021; Journal of Combinatorics and Number Theory 12:3 (2022), 115-155.
%H A010060 Bill Allombert and Alain Lasjaunias, <a href="https://arxiv.org/abs/2505.20102">On a family of continued fractions in Q((T^1)) associated to infinite binary words derived from the Thue-Morse sequence</a>, arXiv:2505.20102 [math.NT], 2025. See p. 2.
%H A010060 J.-P. Allouche, <a href="http://algo.inria.fr/seminars/sem92-93/allouche.pdf">Series and infinite products related to binary expansions of integers</a>, Behaviour, 4.4 (1992): p. 5.
%H A010060 J.-P. Allouche, <a href="http://ssdnm.mimuw.edu.pl/pliki/wyklady/allouche-uj.pdf">Lecture notes on automatic sequences</a>, Krakow October 2013.
%H A010060 J.-P. Allouche, <a href="http://dx.doi.org/10.5802/jtnb.906">Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence</a>, J. de Théorie des Nombres de Bordeaux, 27, no. 2 (2015), 375-388.
%H A010060 Jean-Paul Allouche, <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/121-12221.pdf">On the morphism 1 -> 121, 2 -> 12221</a>, CNRS France, 2024. See p. 3.
%H A010060 Jean-Paul Allouche, <a href="/A026465/a026465.pdf">On the morphism 1 -> 121, 2 -> 12221</a>, Preprint, 2024 [Local copy, with permission]
%H A010060 J.-P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, <a href="http://dx.doi.org/10.1016/0012-365X(93)00147-W">A relative of the Thue-Morse sequence</a>, Discrete Math., 139 (1995), 455-461.
%H A010060 Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit and Luca Q. Zamboni, <a href="https://arxiv.org/abs/1711.10807">A Taxonomy of Morphic Sequences</a>, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017.
%H A010060 J.-P. Allouche and H. Cohen, <a href="https://doi.org/10.1112/blms/17.6.531">Dirichlet Series and Curious Infinite Products</a>, Bull. London Math. Soc. 17, 531-538, 1985.
%H A010060 J.-P. Allouche and T. Johnson, <a href="https://hal.science/hal-02986050v1">Narayana's cows and delayed morphisms</a>, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [The hal link does not always work. - _N. J. A. Sloane_, Feb 19 2025]
%H A010060 J.-P. Allouche and T. Johnson, <a href="/A000930/a000930.pdf">Narayana's cows and delayed morphisms</a>, in G. Assayag, M. Chemillier, and C. Eloy, Troisièmes Journées d'Informatique Musicale, JIM '96, Île de Tatihou, France, 1996, pp. 2-7. [Local copy with annotations and a correction from _N. J. A. Sloane_, Feb 19 2025]
%H A010060 J.-P. Allouche and M. Mendes France, <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/allmendeshouches.pdf">Automata and Automatic Sequences</a>, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
%H A010060 J.-P. Allouche and M. Mendes France, <a href="/A003842/a003842.pdf">Automata and Automatic Sequences</a>, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
%H A010060 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 A010060 J.-P. Allouche and J. Shallit, <a href="http://www.math.jussieu.fr/~allouche/kreg2.ps">The Ring of k-regular Sequences, II</a>, Theoretical Computer Science 307.1 (2003): 3-29. <a href="https://doi.org/10.1016/S0304-3975(03)00090-2">doi:10.1016/S0304-3975(03)00090-2</a>
%H A010060 Jorge Almeida and Ondrej Klíma, <a href="https://arxiv.org/abs/1904.07137">Binary patterns in the Prouhet-Thue-Morse sequence</a>, arXiv:1904.07137 [math.CO], 2019.
%H A010060 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 44.
%H A010060 G. N. Arzhantseva, C. H. Cashen, D. Gruber and D. Hume, <a href="http://arxiv.org/abs/1602.03767">Contracting geodesics in infinitely presented graphical small cancellation groups</a>, arXiv preprint arXiv:1602.03767 [math.GR], 2016-2018.
%H A010060 Ricardo Astudillo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Astudillo/astudillo12.html">On a Class of Thue-Morse Type Sequences</a>, J. Integer Seqs., Vol. 6, 2003.
%H A010060 F. Axel et al., <a href="https://doi.org/10.1051/jphyscol:1986318">Vibrational modes in a one dimensional "quasi-alloy": the Morse case</a>, J. de Physique, Colloq. C3, Supp. to No. 7, Vol. 47 (Jul 1986), pp. C3-181-C3-186; see Eq. (10).
%H A010060 M. Baake, U. Grimm and J. Nilsson, <a href="http://arxiv.org/abs/1311.4371">Scaling of the Thue-Morse diffraction measure</a>, arXiv preprint arXiv:1311.4371 [math-ph], 2013.
%H A010060 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 A010060 Lucilla Baldini and Josef Eschgfäller, <a href="http://arxiv.org/abs/1609.01750">Random functions from coupled dynamical systems</a>, arXiv preprint arXiv:1609.01750 [math.CO], 2016. See Example 3.11.
%H A010060 J. Berstel, <a href="/A010060/a010060.pdf">Axel Thue's papers on repetitions in words: a translation</a>, July 21 1994. Publications du LaCIM, Département de mathématiques et d'informatique 20, Université du Québec à Montréal, 1995, 85 pages. [Cached copy]
%H A010060 J.-F. Bertazzon, <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 A010060 J. Cooper and A. Dutle, <a href="https://www.jstor.org/stable/10.4169/amer.math.monthly.120.05.441">Greedy Galois Games</a>, Amer. Math. Mnthly, 120 (2013), 441-451.
%H A010060 Françoise Dejean, <a href="https://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 A010060 F. Michel Dekking, <a href="http://arxiv.org/abs/1509.00260">Morphisms, Symbolic sequences, and their Standard Forms</a>, arXiv:1509.00260 [math.CO], 2015.
%H A010060 F. M. Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Dekking/dek25.html">The Thue-Morse Sequence in Base 3/2</a>, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
%H A010060 A. de Luca and S. Varricchio, <a href="https://doi.org/10.1016/0304-3975(89)90013-3">Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups</a>, Theoret. Comput. Sci. 63 (1989), 333-348.
%H A010060 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 A010060 M. Drmota, C. Mauduit and J. Rivat, <a href="http://www.dmg.tuwien.ac.at/drmota/alongsquares.pdf">The Thue-Morse Sequence Along The Squares is Normal</a>, Abstract, ÖMG-DMV Congress, 2013.
%H A010060 Arthur Dolgopolov, <a href="https://arthurdolgopolov.net/papers/TM.pdf">Equitable Sequencing and Allocation Under Uncertainty</a>, Preprint, 2016.
%H A010060 J. Endrullis, D. Hendriks and J. W. Klop, <a href="https://www.researchgate.net/profile/Joerg_Endrullis/publication/235711311_Degrees_of_Streams/links/00b495321615fe0696000000.pdf">Degrees of streams</a>, Journal of Integers B 11 (2011): 1-40..
%H A010060 A. S. Fraenkel, <a href="http://www.emis.de/journals/INTEGERS/papers/eg6/eg6.Abstract.html">New games related to old and new sequences</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
%H A010060 Hao Fu and G.-N. Han, <a href="http://arxiv.org/abs/1601.04370">Computer assisted proof for Apwenian sequences related to Hankel determinants</a>, arXiv preprint arXiv:1601.04370 [math.NT], 2016.
%H A010060 Maciej Gawro and Maciej Ulas, "On formal inverse of the Prouhet-Thue-Morse sequence." Discrete Mathematics 339.5 (2016): 1459-1470. Also <a href="http://arxiv.org/abs/1601.04840">arXiv:1601.04840</a>, 2016.
%H A010060 Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>
%H A010060 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 [cs.FL], Jun 28 2012.
%H A010060 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 A010060 Russell Jay Hendel, <a href="https://arxiv.org/abs/2505.20547">A Family of Sequences Generalizing the Thue Morse and Rudin Shapiro Sequences</a>, arXiv:2505.20547 [cs.FL], 2025. See p. 2.
%H A010060 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 [math.CO], 2012.
%H A010060 A. M. Hinz, S. Klavžar, U. Milutinović and 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">Website for book</a>
%H A010060 Denis Janković, Rémi Pasquier, Jean-Gabriel Hartmann, and Paul-Antoine Hervieux, <a href="https://arxiv.org/abs/2501.09610">Elucidating the Physical and Mathematical Properties of the Prouhet-Thue-Morse Sequence in Quantum Computing</a>, arXiv:2501.09610 [quant-ph], 2025. See p. 17.
%H A010060 Tanya Khovanova, <a href="http://arxiv.org/abs/1405.6958">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.
%H A010060 Clark Kimberling, <a href="https://doi.org/10.4171/EM/468">Intriguing infinite words composed of zeros and ones</a>, Elemente der Mathematik (2021).
%H A010060 Naoki Kobayashi, Kazutaka Matsuda and Ayumi Shinohara, <a href="http://www.kb.ecei.tohoku.ac.jp/~koba/papers/pepm2012-full.pdf">Functional Programs as Compressed Data</a>, Higher-Order and Symbolic Computation, 25, no. 1 (2012): 39-84..
%H A010060 Philip Lafrance, Narad Rampersad and Randy Yee, <a href="http://arxiv.org/abs/1408.2277">Some properties of a Rudin-Shapiro-like sequence</a>, arXiv:1408.2277 [math.CO], 2014.
%H A010060 C. Mauduit and J. Rivat, <a href="http://dx.doi.org/10.1007/s11511-009-0040-0">La somme des chiffres des carrés</a>, Acta Mathem. 203 (1) (2009) 107-148.
%H A010060 Harold Marston 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 A010060 F. Mignosi, A. Restivo, and M. Sciortino, <a href="https://doi.org/10.1016/S0304-3975(00)00436-9">Words and forbidden factors</a>, WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096).
%H A010060 Marston Morse, <a href="https://doi.org/10.1090/S0002-9904-1938-06817-6">A solution of the problem of infinite play in chess</a>, (review), Bull. Amer. Math. Soc., 44 (No. 9, 1938), p. 632. [Mentions an application to chess]
%H A010060 K. Nakano, <a href="http://dx.doi.org/10.1007/978-3-642-35308-6_14">Shall We Juggle, Coinductively?</a>, in Certified Programs and Proofs, Lecture Notes in Computer Science Volume 7679, 2012, pp. 160-172.
%H A010060 Hieu D. Nguyen, <a href="http://arxiv.org/abs/1405.6958">A mixing of Prouhet-Thue-Morse sequences and Rademacher functions</a>, arXiv preprint arXiv:1405.6958 [math.NT], 2014.
%H A010060 Hieu D. Nguyen, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Nguyen/nguyen6.html">A Generalization of the Digital Binomial Theorem </a>, J. Int. Seq. 18 (2015) # 15.5.7.
%H A010060 C. D. Offner, <a href="http://www.rw.cdl.uni-saarland.de/~joba/Info3/material/quadratfrei.pdf">Repetitions of Words and the Thue-Morse sequence</a>. Preprint, no date.
%H A010060 Matt Parker, <a href="https://www.youtube.com/watch?v=prh72BLNjIk">The Fairest Sharing Sequence Ever</a>, YouTube video, Nov 27 2015
%H A010060 A. Parreau, M. Rigo, E. Rowland and E. Vandomme, <a href="http://arxiv.org/abs/1405.3532">A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences</a>, arXiv preprint arXiv:1405.3532 [cs.FL], 2014.
%H A010060 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 A010060 Saúl Pilatowsky-Cameo, Soonwon Choi, and Wen Wei Ho, <a href="https://arxiv.org/abs/2502.06936">Critically slow Hilbert-space ergodicity in quantum morphic drives</a>, arXiv:2502.06936 [quant-ph], 2025. See pp. 6, 15.
%H A010060 E. Prouhet, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k29901/f227.item">Mémoire sur quelques relations entre les puissances des nombres</a>, Comptes Rendus Acad. des Sciences, 33 (No. 8, 1851), p. 225. [Said to implicitly mention this sequence]
%H A010060 Michel Rigo, <a href="http://arxiv.org/abs/1602.03364">Relations on words</a>, arXiv preprint arXiv:1602.03364 [cs.FL], 2016.
%H A010060 Luke Schaeffer and Jeffrey Shallit, <a href="https://doi.org/10.37236/5752">Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences</a>, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
%H A010060 M. R. Schroeder & N. J. A. Sloane, <a href="/A005599/a005599.pdf">Correspondence, 1991</a>
%H A010060 R. Schroeppel and R. W. Gosper, <a href="http://www.inwap.com/pdp10/hbaker/hakmem/series.html#item122">HACKMEM #122</a> (1972).
%H A010060 Vladimir Shevelev, <a href="http://arxiv.org/abs/1603.04434">Two analogs of Thue-Morse sequence</a>, arXiv preprint arXiv:1603.04434 [math.NT], 2016-2017.
%H A010060 N. J. A. Sloane, <a href="/A010060/a010060.txt">The first 1000 terms as a string</a>
%H A010060 L. Spiegelhofer, <a href="http://dx.doi.org/10.1093/qmath/hav029">Normality of the Thue-Morse Sequence along Piatetski-Shapiro sequences</a>, Quart. J. Math. 66 (3) (2015).
%H A010060 Hassan Tarfaoui, <a href="http://d.tarfaoui.free.fr/cg/1990/EX1/exobis.pdf">Concours Général 1990 - Exercice 1</a> (in French).
%H A010060 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Thue-MorseSequence.html">Thue-Morse Sequence</a>
%H A010060 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Thue-MorseConstant.html">Thue-Morse Constant</a>
%H A010060 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Parity.html">Parity</a>
%H A010060 Joost Winter, Marcello M. Bonsangue, and Jan J. M. M. Rutten, <a href="http://oai.cwi.nl/oai/asset/21313/21313A.pdf">Context-free coalgebras</a>, Journal of Computer and System Sciences, 81.5 (2015): 911-939.
%H A010060 Hans Zantema, <a href="https://doi.org/10.1007/978-3-030-40608-0_18">Complexity of Automatic Sequences</a>, International Conference on Language and Automata Theory and Applications (LATA 2020): Language and Automata Theory and Applications, 260-271.
%H A010060 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%H A010060 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A010060 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A010060 <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>
%H A010060 <a href="/index/O#Olympiads">Index to sequences related to Olympiads and other Mathematical competitions</a>.
%F A010060 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 A010060 If n = Sum b_i*2^i is the binary expansion of n then a(n) = Sum b_i (mod 2).
%F A010060 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 A010060 G.f.: (1/(1 - x) - Product_{k >= 0} (1 - x^(2^k)))/2. - _Benoit Cloitre_, Apr 23 2003
%F A010060 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 A010060 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 A010060 Let b(1) = 1 and b(n) = b(ceiling(n/2)) - b(floor(n/2)) then a(n-1) = (1/2)*(1 - b(2n-1)). - _Benoit Cloitre_, Apr 26 2005
%F A010060 a(n) = 1 - A010059(n) = A001285(n) - 1. - _Ralf Stephan_, Jun 20 2003
%F A010060 a(n) = A001969(n) - 2n. - _Franklin T. Adams-Watters_, Aug 28 2006
%F A010060 a(n) = A115384(n) - A115384(n-1) for n > 0. - _Reinhard Zumkeller_, Aug 26 2007
%F A010060 For n >= 0, a(A004760(n+1)) = 1 - a(n). - _Vladimir Shevelev_, Apr 25 2009
%F A010060 a(A160217(n)) = 1 - a(n). - _Vladimir Shevelev_, May 05 2009
%F A010060 a(n) == A000069(n) (mod 2). - _Robert G. Wilson v_, Jan 18 2012
%F A010060 a(n) = A000035(A000120(n)). - _Omar E. Pol_, Oct 26 2013
%F A010060 a(n) = A000035(A193231(n)). - _Antti Karttunen_, Dec 27 2013
%F A010060 a(n) + A181155(n-1) = 2n for n >= 1. - _Clark Kimberling_, Oct 06 2014
%F A010060 G.f. A(x) satisfies: A(x) = x / (1 - x^2) + (1 - x) * A(x^2). - _Ilya Gutkovskiy_, Jul 29 2021
%F A010060 From _Bernard Schott_, Jan 21 2022: (Start)
%F A010060 a(n) = a(n*2^k) for k >= 0.
%F A010060 a((2^m-1)^2) = (1-(-1)^m)/2 (see Hassan Tarfaoui link, Concours Général 1990). (End)
%e A010060 The evolution starting at 0 is:
%e A010060 0
%e A010060 0, 1
%e A010060 0, 1, 1, 0
%e A010060 0, 1, 1, 0, 1, 0, 0, 1
%e A010060 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0
%e A010060 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 A010060 .......
%e A010060 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 A010060 From _Joerg Arndt_, Mar 12 2013: (Start)
%e A010060 The first steps of the iterated substitution are
%e A010060 Start: 0
%e A010060 Rules:
%e A010060 0 --> 01
%e A010060 1 --> 10
%e A010060 -------------
%e A010060 0: (#=1)
%e A010060 0
%e A010060 1: (#=2)
%e A010060 01
%e A010060 2: (#=4)
%e A010060 0110
%e A010060 3: (#=8)
%e A010060 01101001
%e A010060 4: (#=16)
%e A010060 0110100110010110
%e A010060 5: (#=32)
%e A010060 01101001100101101001011001101001
%e A010060 6: (#=64)
%e A010060 0110100110010110100101100110100110010110011010010110100110010110
%e A010060 (End)
%e A010060 From _Omar E. Pol_, Oct 28 2013: (Start)
%e A010060 Written as an irregular triangle in which row lengths is A011782, the sequence begins:
%e A010060 0;
%e A010060 1;
%e A010060 1,0;
%e A010060 1,0,0,1;
%e A010060 1,0,0,1,0,1,1,0;
%e A010060 1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1;
%e A010060 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 A010060 It appears that: row j lists the first A011782(j) terms of A010059, with j >= 0; row sums give A166444 which is also 0 together with A011782; right border gives A000035.
%e A010060 (End)
%p A010060 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 A010060 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 A010060:=proc(n)
%p A010060 add(i,i=convert(n, base, 2)) mod 2 ;
%p A010060 end proc:
%p A010060 seq(A010060(n),n=0..104); # _Emeric Deutsch_, Mar 19 2005
%p A010060 map(`-`,convert(StringTools[ThueMorse](1000),bytes),48); # _Robert Israel_, Sep 22 2014
%t A010060 Table[ If[ OddQ[ Count[ IntegerDigits[n, 2], 1]], 1, 0], {n, 0, 100}];
%t A010060 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 A010060 Mod[ Count[ #, 1 ]& /@Table[ IntegerDigits[ i, 2 ], {i, 0, 2^7 - 1} ], 2 ] (* _Harlan J. Brothers_, Feb 05 2005 *)
%t A010060 Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {0}, 7] (* _Robert G. Wilson v_ Sep 26 2006 *)
%t A010060 a[n_] := If[n == 0, 0, If[Mod[n, 2] == 0, a[n/2], 1 - a[(n - 1)/2]]] (* _Ben Branman_, Oct 22 2010 *)
%t A010060 a[n_] := Mod[Length[FixedPointList[BitAnd[#, # - 1] &, n]], 2] (* _Jan Mangaldan_, Jul 23 2015 *)
%t A010060 Table[2/3 (1 - Cos[Pi/3 (n - Sum[(-1)^Binomial[n, k], {k, 1, n}])]), {n, 0, 100}] (* or, for version 10.2 or higher *) Table[ThueMorse[n], {n, 0, 100}] (* _Vladimir Reshetnikov_, May 06 2016 *)
%t A010060 ThueMorse[Range[0, 100]] (* The program uses the ThueMorse function from Mathematica version 11 *) (* _Harvey P. Dale_, Aug 11 2016 *)
%t A010060 Nest[Join[#, 1 - #] &, {0}, 7] (* _Paolo Xausa_, Oct 25 2024 *)
%o A010060 (Haskell)
%o A010060 a010060 n = a010060_list !! n
%o A010060 a010060_list =
%o A010060 0 : interleave (complement a010060_list) (tail a010060_list)
%o A010060 where complement = map (1 - )
%o A010060 interleave (x:xs) ys = x : interleave ys xs
%o A010060 -- Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 29 2003
%o A010060 -- Edited by _Reinhard Zumkeller_, Oct 03 2012
%o A010060 (PARI) a(n)=if(n<1,0,sum(k=0,length(binary(n))-1,bittest(n,k))%2)
%o A010060 (PARI) a(n)=if(n<1,0,subst(Pol(binary(n)), x,1)%2)
%o A010060 (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)); \\ _Harry J. Smith_, Apr 28 2009
%o A010060 (PARI) a(n)=hammingweight(n)%2 \\ _Charles R Greathouse IV_, Mar 22 2013
%o A010060 (Python)
%o A010060 A010060_list = [0]
%o A010060 for _ in range(14):
%o A010060 A010060_list += [1-d for d in A010060_list] # _Chai Wah Wu_, Mar 04 2016
%o A010060 (Python)
%o A010060 def A010060(n): return n.bit_count()&1 # _Chai Wah Wu_, Mar 01 2023
%o A010060 (R)
%o A010060 maxrow <- 8 # by choice
%o A010060 b01 <- 1
%o A010060 for(m in 0:maxrow) for(k in 0:(2^m-1)){
%o A010060 b01[2^(m+1)+ k] <- b01[2^m+k]
%o A010060 b01[2^(m+1)+2^m+k] <- 1-b01[2^m+k]
%o A010060 }
%o A010060 (b01 <- c(0,b01))
%o A010060 # _Yosu Yurramendi_, Apr 10 2017
%Y A010060 Cf. A001285 (for 1, 2 version), A010059 (for 1, 0 version), A106400 (for +1, -1 version), A048707. A010060(n)=A000120(n) mod 2.
%Y A010060 Cf. A007413, A080813, A080814, A036581, A108694. See also the Thue (or Roth) constant A014578, also A014571.
%Y A010060 Cf. also A001969, A035263, A005187, A115384, A132680, A141803, A104248, A193231.
%Y A010060 Run lengths give A026465. Backward first differences give A029883.
%Y A010060 Cf. A004128, A053838, A059448, A171900, A161916, A214212, A005942 (subword complexity), A010693 (Abelian complexity), A225186 (squares), A228039 (a(n^2)), A282317.
%Y A010060 Sequences mentioned in the Allouche et al. "Taxonomy" paper, listed by example number: 1: A003849, 2: A010060, 3: A010056, 4: A020985 and A020987, 5: A191818, 6: A316340 and A273129, 18: A316341, 19: A030302, 20: A063438, 21: A316342, 22: A316343, 23: A003849 minus its first term, 24: A316344, 25: A316345 and A316824, 26: A020985 and A020987, 27: A316825, 28: A159689, 29: A049320, 30: A003849, 31: A316826, 32: A316827, 33: A316828, 34: A316344, 35: A043529, 36: A316829, 37: A010060.
%K A010060 nonn,core,easy,nice
%O A010060 0,1
%A A010060 _N. J. A. Sloane_