A020987 -id:A020987 - cp's OEIS frontend

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.

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, 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, 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

Offset: 0

N. J. A. Sloane

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
Also called the Thue-Morse infinite word, or the Morse-Hedlund sequence, or the parity sequence.
Fixed point of the morphism 0 --> 01, 1 --> 10, see example. - Joerg Arndt, Mar 12 2013
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).
a(n) = "parity sequence" = parity of number of 1's in binary representation of n.
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
Characteristic function of A000069 (odious numbers). - Ralf Stephan, Jun 20 2003
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)
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
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
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
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
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.
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.
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.
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.
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
"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.
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
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
Drmota, Mauduit, and Rivat proved that the subsequence a(n^2) is normal--see A228039. - Jonathan Sondow, Sep 03 2013
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
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

			The evolution starting at 0 is:
  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, 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
  .......
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.
From _Joerg Arndt_, Mar 12 2013: (Start)
The first steps of the iterated substitution are
Start: 0
Rules:
  0 --> 01
  1 --> 10
-------------
0:   (#=1)
  0
1:   (#=2)
  01
2:   (#=4)
  0110
3:   (#=8)
  01101001
4:   (#=16)
  0110100110010110
5:   (#=32)
  01101001100101101001011001101001
6:   (#=64)
  0110100110010110100101100110100110010110011010010110100110010110
(End)
From _Omar E. Pol_, Oct 28 2013: (Start)
Written as an irregular triangle in which row lengths is A011782, the sequence begins:
  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,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;
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.
(End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 15.
Jason Bell, Michael Coons, and Eric Rowland, "The Rational-Transcendental Dichotomy of Mahler Functions", Journal of Integer Sequences, Vol. 16 (2013), #13.2.10.
J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
B. Bollobas, The Art of Mathematics: Coffee Time in Memphis, Cambridge, 2006, p. 224.
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.
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.
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.
Currie, James D. "Non-repetitive words: Ages and essences." Combinatorica 16.1 (1996): 19-40
Colin Defant, Anti-Power Prefixes of the Thue-Morse Word, Journal of Combinatorics, 24(1) (2017), #P1.32
F. M. Dekking, Transcendance du nombre de Thue-Morse, Comptes Rendus de l'Academie des Sciences de Paris 285 (1977), pp. 157-160.
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)
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).
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).
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.
M. Euwe, Mengentheoretische Betrachtungen Über das Schachspiel, Proceedings Koninklijke Nederlandse Akademie van Wetenschappen, Amsterdam, Vol. 32 (5): 633-642, 1929.
S. Ferenczi, Complexity of sequences and dynamical systems, Discrete Math., 206 (1999), 145-154.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.8.
W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149-159.
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.
B. Kitchens, Review of "Computational Ergodic Theory" by G. H. Choe, Bull. Amer. Math. Soc., 44 (2007), 147-155.
Le Breton, Xavier, Linear independence of automatic formal power series. Discrete Math. 306 (2006), no. 15, 1776-1780.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.
Donald MacMurray, A mathematician gives an hour to chess, Chess Review 6 (No. 10, 1938), 238. [Discusses Marston's 1938 article]
Mauduit, Christian. Multiplicative properties of the Thue-Morse sequence. Period. Math. Hungar. 43 (2001), no. 1-2, 137--153. MR1830572 (2002i:11081)
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.
C. A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 60.
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.
Narad Rampersad and Elise Vaslet, "On Highly Repetitive and Power Free Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.7.
G. Richomme, K. Saari, L. Q. Zamboni, Abelian complexity in minimal subshifts, J. London Math. Soc. 83(1) (2011) 79-95.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
M. Rigo, P. Salimov, and E. Vandomme, "Some Properties of Abelian Return Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
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).
A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.
Shallit, J. O. "On Infinite Products Associated with Sums of Digits." J. Number Th. 21, 128-134, 1985.
Ian Stewart, "Feedback", Mathematical Recreations Column, Scientific American, 274 (No. 3, 1996), page 109 [Historical notes on this sequence]
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. .
A. Thue. Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, No. 7 (1906), 1-22.
A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 1 (1912), 1-67.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 890.

N. J. A. Sloane, Table of n, a(n) for n = 0..16383
A. G. M. Ahmed, AA Weaving. In: Proceedings of Bridges 2013: Mathematics, Music, Art, ..., 2013.
A. Aksenov, The Newman phenomenon and Lucas sequence, arXiv preprint arXiv:1108.5352 [math.NT], 2011-2012.
Max A. Alekseyev and N. J. A. Sloane, On Kaprekar's Junction Numbers, arXiv:2112.14365, 2021; Journal of Combinatorics and Number Theory 12:3 (2022), 115-155.
Bill Allombert and Alain Lasjaunias, On a family of continued fractions in Q((T^1)) associated to infinite binary words derived from the Thue-Morse sequence, arXiv:2505.20102 [math.NT], 2025. See p. 2.
J.-P. Allouche, Series and infinite products related to binary expansions of integers, Behaviour, 4.4 (1992): p. 5.
J.-P. Allouche, Lecture notes on automatic sequences, Krakow October 2013.
J.-P. Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, J. de Théorie des Nombres de Bordeaux, 27, no. 2 (2015), 375-388.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See p. 3.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
J.-P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, A relative of the Thue-Morse sequence, Discrete Math., 139 (1995), 455-461.
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017.
J.-P. Allouche and H. Cohen, Dirichlet Series and Curious Infinite Products, Bull. London Math. Soc. 17, 531-538, 1985.
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, 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]
J.-P. Allouche and T. Johnson, Narayana's cows and delayed morphisms, 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]
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, 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.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, 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]
J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II, Theoretical Computer Science 307.1 (2003): 3-29. doi:10.1016/S0304-3975(03)00090-2
Jorge Almeida and Ondrej Klíma, Binary patterns in the Prouhet-Thue-Morse sequence, arXiv:1904.07137 [math.CO], 2019.
Joerg Arndt, Matters Computational (The Fxtbook), p. 44.
G. N. Arzhantseva, C. H. Cashen, D. Gruber and D. Hume, Contracting geodesics in infinitely presented graphical small cancellation groups, arXiv preprint arXiv:1602.03767 [math.GR], 2016-2018.
Ricardo Astudillo, On a Class of Thue-Morse Type Sequences, J. Integer Seqs., Vol. 6, 2003.
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).
M. Baake, U. Grimm and J. Nilsson, Scaling of the Thue-Morse diffraction measure, arXiv preprint arXiv:1311.4371 [math-ph], 2013.
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
Lucilla Baldini and Josef Eschgfäller, Random functions from coupled dynamical systems, arXiv preprint arXiv:1609.01750 [math.CO], 2016. See Example 3.11.
J. Berstel, Axel Thue's papers on repetitions in words: a translation, 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]
J.-F. Bertazzon, Resolution of an integral equation with the Thue-Morse sequence, arXiv:1201.2502v1 [math.CO], Jan 12, 2012.
J. Cooper and A. Dutle, Greedy Galois Games, Amer. Math. Mnthly, 120 (2013), 441-451.
Françoise Dejean, Sur un Théorème de Thue, J. Combinatorial Theory, vol. 13 A, iss. 1 (1972) 90-99.
F. Michel Dekking, Morphisms, Symbolic sequences, and their Standard Forms, arXiv:1509.00260 [math.CO], 2015.
F. M. Dekking, The Thue-Morse Sequence in Base 3/2, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
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.
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.
M. Drmota, C. Mauduit and J. Rivat, The Thue-Morse Sequence Along The Squares is Normal, Abstract, ÖMG-DMV Congress, 2013.
Arthur Dolgopolov, Equitable Sequencing and Allocation Under Uncertainty, Preprint, 2016.
J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams, Journal of Integers B 11 (2011): 1-40..
A. S. Fraenkel, New games related to old and new sequences, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
Hao Fu and G.-N. Han, Computer assisted proof for Apwenian sequences related to Hankel determinants, arXiv preprint arXiv:1601.04370 [math.NT], 2016.
Maciej Gawro and Maciej Ulas, "On formal inverse of the Prouhet-Thue-Morse sequence." Discrete Mathematics 339.5 (2016): 1459-1470. Also arXiv:1601.04840, 2016.
Michael Gilleland, Some Self-Similar Integer Sequences
Daniel Goc, Luke Schaeffer and Jeffrey Shallit, The Subword Complexity of k-Automatic Sequences is k-Synchronized, arXiv 1206.5352 [cs.FL], Jun 28 2012.
G. A. Hedlund, Remarks on the work of Axel Thue on sequences, Nordisk Mat. Tid., 15 (1967), 148-150.
Russell Jay Hendel, A Family of Sequences Generalizing the Thue Morse and Rudin Shapiro Sequences, arXiv:2505.20547 [cs.FL], 2025. See p. 2.
Dimitri Hendriks, Frits G. W. Dannenberg, Jorg Endrullis, Mark Dow and Jan Willem Klop, Arithmetic Self-Similarity of Infinite Sequences, arXiv preprint 1201.3786 [math.CO], 2012.
A. M. Hinz, S. Klavžar, U. Milutinović and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 79. Website for book
Denis Janković, Rémi Pasquier, Jean-Gabriel Hartmann, and Paul-Antoine Hervieux, Elucidating the Physical and Mathematical Properties of the Prouhet-Thue-Morse Sequence in Quantum Computing, arXiv:2501.09610 [quant-ph], 2025. See p. 17.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Clark Kimberling, Intriguing infinite words composed of zeros and ones, Elemente der Mathematik (2021).
Naoki Kobayashi, Kazutaka Matsuda and Ayumi Shinohara, Functional Programs as Compressed Data, Higher-Order and Symbolic Computation, 25, no. 1 (2012): 39-84..
Philip Lafrance, Narad Rampersad and Randy Yee, Some properties of a Rudin-Shapiro-like sequence, arXiv:1408.2277 [math.CO], 2014.
C. Mauduit and J. Rivat, La somme des chiffres des carrés, Acta Mathem. 203 (1) (2009) 107-148.
Harold Marston Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22 (1921), 84-100.
F. Mignosi, A. Restivo, and M. Sciortino, Words and forbidden factors, WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096).
Marston Morse, A solution of the problem of infinite play in chess, (review), Bull. Amer. Math. Soc., 44 (No. 9, 1938), p. 632. [Mentions an application to chess]
K. Nakano, Shall We Juggle, Coinductively?, in Certified Programs and Proofs, Lecture Notes in Computer Science Volume 7679, 2012, pp. 160-172.
Hieu D. Nguyen, A mixing of Prouhet-Thue-Morse sequences and Rademacher functions, arXiv preprint arXiv:1405.6958 [math.NT], 2014.
Hieu D. Nguyen, A Generalization of the Digital Binomial Theorem , J. Int. Seq. 18 (2015) # 15.5.7.
C. D. Offner, Repetitions of Words and the Thue-Morse sequence. Preprint, no date.
Matt Parker, The Fairest Sharing Sequence Ever, YouTube video, Nov 27 2015
A. Parreau, M. Rigo, E. Rowland and E. Vandomme, A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences, arXiv preprint arXiv:1405.3532 [cs.FL], 2014.
C. A. Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," Zentralblatt review
Saúl Pilatowsky-Cameo, Soonwon Choi, and Wen Wei Ho, Critically slow Hilbert-space ergodicity in quantum morphic drives, arXiv:2502.06936 [quant-ph], 2025. See pp. 6, 15.
E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres, Comptes Rendus Acad. des Sciences, 33 (No. 8, 1851), p. 225. [Said to implicitly mention this sequence]
Michel Rigo, Relations on words, arXiv preprint arXiv:1602.03364 [cs.FL], 2016.
Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
M. R. Schroeder & N. J. A. Sloane, Correspondence, 1991
R. Schroeppel and R. W. Gosper, HACKMEM #122 (1972).
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv preprint arXiv:1603.04434 [math.NT], 2016-2017.
N. J. A. Sloane, The first 1000 terms as a string
L. Spiegelhofer, Normality of the Thue-Morse Sequence along Piatetski-Shapiro sequences, Quart. J. Math. 66 (3) (2015).
Hassan Tarfaoui, Concours Général 1990 - Exercice 1 (in French).
Eric Weisstein's World of Mathematics, Thue-Morse Sequence
Eric Weisstein's World of Mathematics, Thue-Morse Constant
Eric Weisstein's World of Mathematics, Parity
Joost Winter, Marcello M. Bonsangue, and Jan J. M. M. Rutten, Context-free coalgebras, Journal of Computer and System Sciences, 81.5 (2015): 911-939.
Hans Zantema, Complexity of Automatic Sequences, International Conference on Language and Automata Theory and Applications (LATA 2020): Language and Automata Theory and Applications, 260-271.
Index entries for sequences that are fixed points of mappings
Index entries for "core" sequences
Index entries for sequences related to binary expansion of n
Index entries for characteristic functions
Index to sequences related to Olympiads and other Mathematical competitions.

Cf. A001285 (for 1, 2 version), A010059 (for 1, 0 version), A106400 (for +1, -1 version), A048707. A010060(n)=A000120(n) mod 2.
Cf. A007413, A080813, A080814, A036581, A108694. See also the Thue (or Roth) constant A014578, also A014571.
Cf. also A001969, A035263, A005187, A115384, A132680, A141803, A104248, A193231.
Run lengths give A026465. Backward first differences give A029883.
Cf. A004128, A053838, A059448, A171900, A161916, A214212, A005942 (subword complexity), A010693 (Abelian complexity), A225186 (squares), A228039 (a(n^2)), A282317.
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.

a010060 n = a010060_list !! n
a010060_list =
   0 : interleave (complement a010060_list) (tail a010060_list)
   where complement = map (1 - )
         interleave (x:xs) ys = x : interleave ys xs
-- Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 29 2003
-- Edited by Reinhard Zumkeller, Oct 03 2012

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.
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]]]]
A010060:=proc(n)
    add(i,i=convert(n, base, 2)) mod 2 ;
end proc:
seq(A010060(n),n=0..104); # Emeric Deutsch, Mar 19 2005
map(`-`,convert(StringTools[ThueMorse](1000),bytes),48); # Robert Israel, Sep 22 2014

Table[ If[ OddQ[ Count[ IntegerDigits[n, 2], 1]], 1, 0], {n, 0, 100}];
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]
Mod[ Count[ #, 1 ]& /@Table[ IntegerDigits[ i, 2 ], {i, 0, 2^7 - 1} ], 2 ] (* Harlan J. Brothers, Feb 05 2005 *)
Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {0}, 7] (* Robert G. Wilson v Sep 26 2006 *)
a[n_] := If[n == 0, 0, If[Mod[n, 2] == 0, a[n/2], 1 - a[(n - 1)/2]]] (* Ben Branman, Oct 22 2010 *)
a[n_] := Mod[Length[FixedPointList[BitAnd[#, # - 1] &, n]], 2] (* Jan Mangaldan, Jul 23 2015 *)
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 *)
ThueMorse[Range[0, 100]] (* The program uses the ThueMorse function from Mathematica version 11 *) (* Harvey P. Dale, Aug 11 2016 *)
Nest[Join[#, 1 - #] &, {0}, 7] (* Paolo Xausa, Oct 25 2024 *)

a(n)=if(n<1,0,sum(k=0,length(binary(n))-1,bittest(n,k))%2)

a(n)=if(n<1,0,subst(Pol(binary(n)), x,1)%2)

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

a(n)=hammingweight(n)%2 \\ Charles R Greathouse IV, Mar 22 2013

A010060_list = [0]
for _ in range(14):
    A010060_list += [1-d for d in A010060_list] # Chai Wah Wu, Mar 04 2016

def A010060(n): return n.bit_count()&1 # Chai Wah Wu, Mar 01 2023

maxrow <- 8 # by choice
b01 <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)){
b01[2^(m+1)+    k] <-   b01[2^m+k]
b01[2^(m+1)+2^m+k] <- 1-b01[2^m+k]
}
(b01 <- c(0,b01))
# Yosu Yurramendi, Apr 10 2017

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.
If n = Sum b_i*2^i is the binary expansion of n then a(n) = Sum b_i (mod 2).
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).
G.f.: (1/(1 - x) - Product_{k >= 0} (1 - x^(2^k)))/2. - Benoit Cloitre, Apr 23 2003
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
a(n) = -1 + (Sum_{k=0..n} binomial(n,k) mod 2) mod 3 = -1 + A001316(n) mod 3. - Benoit Cloitre, May 09 2004
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
a(n) = 1 - A010059(n) = A001285(n) - 1. - Ralf Stephan, Jun 20 2003
a(n) = A001969(n) - 2n. - Franklin T. Adams-Watters, Aug 28 2006
a(n) = A115384(n) - A115384(n-1) for n > 0. - Reinhard Zumkeller, Aug 26 2007
For n >= 0, a(A004760(n+1)) = 1 - a(n). - Vladimir Shevelev, Apr 25 2009
a(A160217(n)) = 1 - a(n). - Vladimir Shevelev, May 05 2009
a(n) == A000069(n) (mod 2). - Robert G. Wilson v, Jan 18 2012
a(n) = A000035(A000120(n)). - Omar E. Pol, Oct 26 2013
a(n) = A000035(A193231(n)). - Antti Karttunen, Dec 27 2013
a(n) + A181155(n-1) = 2n for n >= 1. - Clark Kimberling, Oct 06 2014
G.f. A(x) satisfies: A(x) = x / (1 - x^2) + (1 - x) * A(x^2). - Ilya Gutkovskiy, Jul 29 2021
From Bernard Schott, Jan 21 2022: (Start)
a(n) = a(n*2^k) for k >= 0.
a((2^m-1)^2) = (1-(-1)^m)/2 (see Hassan Tarfaoui link, Concours Général 1990). (End)

A003849 The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit).

Original entry on oeis.org

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1

Offset: 0

N. J. A. Sloane

A Sturmian word.
Define strings S(0)=0, S(1)=01, S(n)=S(n-1)S(n-2); iterate; sequence is S(infinity). If the initial 0 is omitted from S(n) for n>0, we obtain A288582(n+1).
The 0's occur at positions in A022342 (i.e., A000201 - 1), the 1's at positions in A003622.
Replace each run (1;1) with (1;0) in the infinite Fibonacci word A005614 (and add 0 as prefix) A005614 begins: 1,0,1,1,0,1,0,1,1,0,1,1,... changing runs (1,1) with (1,0) produces 1,0,0,1,0,1,0,0,1,0,0,1,... - Benoit Cloitre, Nov 10 2003
Characteristic function of A003622. - Philippe Deléham, May 03 2004
The fraction of 0's in the first n terms approaches 1/phi (see for example Allouche and Shallit). - N. J. A. Sloane, Sep 24 2007
The limiting mean and variance of the first n terms are 2-phi and 2*phi-3, respectively. - Clark Kimberling, Mar 12 2014, Aug 16 2018
Let S(n) be defined as above. Then this sequence is S(1) + Sum_{n=0..} S(n), where the addition of strings represents concatenation. - Isaac Saffold, May 03 2019
The word is a concatenation of three runs: 0, 1, and 00. The limiting proportions of these are respectively 1 - phi/2, 1/2, and (phi - 1)/2. The mean runlength is (phi + 1)/2. - Clark Kimberling, Dec 26 2010
From Amiram Eldar, Mar 10 2021: (Start)
a(n) is the number of the trailing 0's in the dual Zeckendorf representation of (n+1) (A104326).
The asymptotic density of the occurrences of k (0 or 1) is 1/phi^(k+1), where phi is the golden ratio (A001622).
The asymptotic mean of this sequence is 1/phi^2 (A132338). (End)

			The word is 010010100100101001010010010100...
Over the alphabet {a,b} this is a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, ...

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
Jean Berstel, Fibonacci words—a survey, In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc. - see p. 64.
Wolfdieter Lang, The Wythoff and the Zeckendorf representations of numbers are equivalent, in G. E. Bergum et al. (edts.) Application of Fibonacci numbers vol. 6, Kluwer, Dordrecht, 1996, pp. 319-337. [See A317208 for a link.]
G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

N. J. A. Sloane, Table of n, a(n) for n = 0..10945
A. G. M. Ahmed, AA Weaving, in Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture.
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, 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.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, 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]
P. Arnoux and E. Harriss, What is a Rauzy Fractal?, Notices Amer. Math. Soc., 61 (No. 7, 2014), 768-770, also p. 704 and front cover.
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
Galyna Barabash, Yaroslav Kholyavka, and Iryna Tytar, Periodic words connected with the Lucas numbers, Visnyk of the Lviv Univ. Series Mech. Math. (2017), Issue 84, 62-66.
Jean Berstel, Home Page
J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
Bryce Emerson Blackham, Subtraction Games: Range and Strict Periodicity, Master's thesis, 2018.
Cristian Cobeli and Alexandru Zaharescu, A bias parity question for Sturmian words, arXiv:1811.06509 [math.NT], 2018.
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.
J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams.
S. Ferenczi, Complexity of sequences and dynamical systems, Discrete Math., 206 (1999), 145-154.
L. Goldberg and A. V. Fraenkel, Patterns in the generalized Fibonacci word, applied to games, Discrete Math., 341 2018 1675-1687.
J. Grytczuk, Infinite semi-similar words, Discrete Math. 161 (1996), 133-141.
Andreas M. Hinz and Paul K. Stockmeyer, Discovering Fibonacci Numbers, Fibonacci Words, and a Fibonacci Fractal in the Tower of Hanoi, The Fibonacci Quarterly (2019) Vol. 57, No. 5, 72-83.
A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149-159.
Tyler Hoffman and B. Steinhurst, Hausdorff Dimension of Generalized Fibonacci Word Fractals, arXiv preprint arXiv:1601.04786 [math.MG], 2016.
T. Karki, A. Lacroix, and M. Rigo, On the recognizability of self-generating sets, JIS 13 (2010) #10.2.2.
Clark Kimberling, A Self-Generating Set and the Golden Mean, J. Integer Sequences, 3 (2000), #00.2.8.
Clark Kimberling, Intriguing infinite words composed of zeros and ones, Elemente der Mathematik (2021).
Eve Kivivuori, Implementing, analyzing, and benchmarking the Relative Lempel-Ziv compression algorithm, Master's Thesis, Univ. Helsinki (Finland 2023).
M. Lothaire, Algebraic Combinatorics on Words, Cambridge, 2002, see p. 41, etc.
Frédéric Mansuy, "Palindromic" and "Quasi-crystalline" characteristics of the sequence and Fibonacci words., hal-02082456, 2019.
Douglas M. McKenna, On a Better Golden Rectangle (That Is Not 61.8033...% Useless!), Proceedings of Bridges (2018), 187-194.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
F. Mignosi, A. Restivo, and M. Sciortino, 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
Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013
Kerry Mitchell, Spirolateral image for this sequence [taken, with permission, from the Spirolateral-Type Images from Integer Sequences article]
T. D. Noe, The first 1652 subwords, including leading zeros.
Saúl Pilatowsky-Cameo, Soonwon Choi, and Wen Wei Ho, Critically slow Hilbert-space ergodicity in quantum morphic drives, arXiv:2502.06936 [quant-ph], 2025. See p. 15.
Giuseppe Pirillo, Fibonacci numbers and words, Discrete Math. 173 (1997), no. 1-3, 197--207. MR1468849 (98g:68135)
J. L. Ramírez and G. N. Rubiano, Properties and Generalizations of the Fibonacci Word Fractal, The Mathematica Journal, Vol. 16 (2014).
José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368 [cs.DM], 2012.
Aayush Rajasekaran, Using Automata Theory to Solve Problems in Additive Number Theory, MS thesis, University of Waterloo, 2018.
Aayush Rajasekaran, Narad Rampersad, and Jeffrey Shallit, Overpals, Underlaps, and Underpals, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.
M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Golden Ratio
Jiemeng Zhang, Zhixiong Wen, and Wen Wu, Some Properties of the Fibonacci Sequence on an Infinite Alphabet, Electronic Journal of Combinatorics, 24(2) (2017), #P2.52.
Index entries for sequences that are fixed points of mappings
Index entries for characteristic functions

There are several versions of this sequence in the OEIS. This one and A003842 are probably the most important. See also A008352, A076662, A288581, A288582.
Binary complement of A005614. Cf. A014675, A036299, A003714, A014417, A096268, A096270, A133235, A182028, A213975.
Positions of 1's gives A003622.
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.
Cf. A001622, A104326, A132338.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

a003849 n = a003849_list !! n
a003849_list = tail $ concat fws where
   fws = [1] : [0] : (zipWith (++) fws $ tail fws)
-- Reinhard Zumkeller, Nov 01 2013, Apr 07 2012

t1:=[ n le 2 select ["0","0,1"][n] else Self(n-1) cat "," cat Self(n-2) : n in [1..12]]; t1[12];

z := proc(m) option remember; if m=0 then [0] elif m=1 then [0,1] else [op(z(m-1)),op(z(m-2))]; fi; end; z(12);
M:=19; S[0]:=`0`; S[1]:=`01`; for n from 2 to M do S[n]:=cat(S[n-1], S[n-2]); od:
t0:=S[M]: l:=length(t0); for i from 1 to l do lprint(i-1,substring(t0,i..i)); od: # N. J. A. Sloane, Nov 01 2006

Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 10] (* Robert G. Wilson v, Mar 05 2005 *)
Flatten[Nest[{#, #[[1]]} &, {0, 1}, 9]] (* IWABUCHI Yu(u)ki, Oct 23 2013 *)
Table[Floor[(n + 2) #] - Floor[(n + 1) #], {n, 0, 120}] &[2 - GoldenRatio] (* Michael De Vlieger, Aug 15 2016 *)
SubstitutionSystem[{0->{0,1},1->{0}},{0},{10}][[1]] (* Harvey P. Dale, Dec 20 2021 *)

a(n)=my(k=2);while(fibonacci(k)<=n,k++);while(n>1,while(fibonacci(k--)>n,); n-=fibonacci(k)); n==1 \\ Charles R Greathouse IV, Feb 03 2014

M3849=[2,2,1,0]/*L(k),S(k),L(k-1),S(k-1)*/; A003849(n)={while(n>M3849[1],M3849=vecextract(M3849,[1,2,1,2])+[M3849[3],M3849[4]<M. F. Hasler, Apr 07 2021

def fib(n):
    """Return the concatenation of A003849(0..F-1) where F is the smallest
       Fibonacci number > n, so that the result contains a(n) at index n."""
    a, b = '10'
    while len(b)<=n:
        a, b = b, b + a
    return b # Robert FERREOL, Apr 15 2016, edited by M. F. Hasler, Apr 07 2021

from math import isqrt
def A003849(n): return 2-(n+2+isqrt(m:=5*(n+2)**2)>>1)+(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 25 2022

a(n) = floor((n+2)*r) - floor((n+1)*r) where r=phi/(1+2*phi) and phi is the Golden Ratio. - Benoit Cloitre, Nov 10 2003
a(n) = A003714(n) mod 2 = A014417(n) mod 2. - Philippe Deléham, Jan 04 2004
The first formula by Cloitre is just one of an infinite family of formulas. Using phi^2=1+phi, it follows that r=phi/(1+2*phi)=2-phi. Then from floor(-x)=-floor(x)-1 for non-integer x, it follows that a(n)=2-A014675(n)=2-(floor((n+2)* phi)-floor((n+1)*phi)). - Michel Dekking, Aug 27 2016
a(n) = 1 - A096270(n+1), i.e., A096270 is the complement of this sequence. - A.H.M. Smeets, Mar 31 2024

Revised by N. J. A. Sloane, Jul 03 2012

A030302 Write n in base 2 and juxtapose; irregular table in which row n lists the binary expansion of n.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 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, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1

Offset: 1

Clark Kimberling

The binary Champernowne constant: it is normal in base 2. - Jason Kimberley, Dec 07 2012
A word that is recurrent, but neither morphic nor uniformly recurrent. - N. J. A. Sloane, Jul 14 2018
See A030303 for the indices of 1's (so this is the characteristic function of A030303), with first differences (i.e., run lengths of 0's, increased by 1, with two consecutive 1's delimiting a run of zero 0's) given by A066099. - M. F. Hasler, Oct 12 2020

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

R. J. Mathar, Table of n, a(n) for n = 1..3998
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017.

Essentially the same as A007088 and A030190. Cf. A030303, A007088.
Tables in which the n-th row lists the base b digits of n: A030190 and this sequence (b=2), A003137 and A054635 (b=3), A030373 (b=4), A031219 (b=5), A030548 (b=6), A030998 (b=7), A031035 and A054634 (b=8), A031076 (b=9), A007376 and A033307 (b=10). [Jason Kimberley, Dec 06 2012]
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.

&cat[Reverse(IntegerToSequence(n,2)): n in [1..31]]; // Jason Kimberley, Mar 02 2012

A030302 := proc(n) local i,t1,t2; t1:=convert(n,base,2); t2:=nops(t1); [seq(t1[t2+1-i],i=1..t2)]; end; # N. J. A. Sloane, Apr 08 2021

i[n_] := Ceiling[FullSimplify[ProductLog[Log[2]/2 (n - 1)]/Log[2] + 1]]; a[n_] := Mod[Floor[2^(Mod[n + 2^i[n] - 2, i[n]] - i[n] + 1) Ceiling[(n + 2^i[n] - 1)/i[n] - 1]], 2]; (* David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007 *)
Join @@ Table[ IntegerDigits[i, 2], {i, 1, 40}] (* Olivier Gérard, Mar 28 2011 *)
Flatten@ IntegerDigits[ Range@ 25, 2] (* or *)
almostNatural[n_, b_] := Block[{m = 0, d = n, i = 1, l, p}, While[m <= d, l = m; m = (b - 1) i*b^(i - 1) + l; i++]; i--; p = Mod[d - l, i]; q = Floor[(d - l)/i] + b^(i - 1); If[p != 0, IntegerDigits[q, b][[p]], Mod[q - 1, b]]]; Array[ almostNatural[#, 2] &, 105] (* Robert G. Wilson v, Jun 29 2014 *)

from itertools import count, islice
def A030302_gen(): # generator of terms
    return (int(d) for n in count(1) for d in bin(n)[2:])
A030302_list = list(islice(A030302_gen(),30)) # Chai Wah Wu, Feb 18 2022

a(n) = (floor(2^(((n + 2^i - 2) mod i) - i + 1) * ceiling((n + 2^i - 1)/i - 1))) mod 2 where i = ceiling( W(log(2)/2 (n - 1))/log(2) + 1 ) and W denotes the principal branch of the Lambert W function. See also Mathematica code. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007

A010056 Characteristic function of Fibonacci numbers: a(n) = 1 if n is a Fibonacci number, otherwise 0.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane

Understood as a binary number, Sum_{k>=0} a(k)/2^k, the resulting decimal expansion is 1.910278797207865891... = Fibonacci_binary+0.5 (see A084119) or Fibonacci_binary_constant-0.5 (see A124091), respectively. - Hieronymus Fischer, May 14 2007
a(n)=1 if and only if there is an integer m such that x=n is a root of p(x)=25*x^4-10*m^2*x^2+m^4-16. Also a(n)=1 iff floor(s)<>floor(c) or ceiling(s)<>ceiling(c) where s=arcsinh(sqrt(5)*n/2)/log(phi), c=arccosh(sqrt(5)*n/2)/log(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, May 17 2007
a(A000045(n)) = 1; a(A001690(n)) = 0. - Reinhard Zumkeller, Oct 10 2013
Image, under the map sending a,b,c -> 1, d,e,f -> 0, of the fixed point, starting with a, of the morphism sending a -> ab, b -> c, c -> cd, d -> d, e -> ef, f -> e. - Jeffrey Shallit, May 14 2016

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017.
D. Bailey et al., On the binary expansions of algebraic numbers, Journal de Théorie des Nombres de Bordeaux (2004), Volume: 16, Issue: 3, page 487-518.
Wikipedia, Fibonacci number
Index entries for characteristic functions

Cf. A000045, A001690, A072649, A104162, A108852, A124091, A130233, A130234.
Decimal expansion of Fibonacci binary is in A084119.
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.
Cf. A079586 (Dirich. g.f. at s=1).

import Data.List (genericIndex)
a010056 = genericIndex a010056_list
a010056_list = 1 : 1 : ch [2..] (drop 3 a000045_list) where
   ch (x:xs) fs'@(f:fs) = if x == f then 1 : ch xs fs else 0 : ch xs fs'
-- Reinhard Zumkeller, Oct 10 2013

a:= n-> (t-> `if`(issqr(t+4) or issqr(t-4), 1, 0))(5*n^2):
seq(a(n), n=0..144);  # Alois P. Heinz, Dec 06 2020

Join[{1},With[{fibs=Fibonacci[Range[15]]},If[MemberQ[fibs,#],1,0]& /@Range[100]]]  (* Harvey P. Dale, May 02 2011 *)

a(n)=my(k=n^2);k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8)) \\ Charles R Greathouse IV, Jul 30 2012

from sympy.ntheory.primetest import is_square
def A010056(n): return int(is_square(m:=5*n**2-4) or is_square(m+8)) # Chai Wah Wu, Mar 30 2023

G.f.: (Sum_{k>=0} x^A000045(k)) - x. - Hieronymus Fischer, May 17 2007

A020985 The Rudin-Shapiro or Golay-Rudin-Shapiro sequence (coefficients of the Shapiro polynomials).

Original entry on oeis.org

1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1

Offset: 0

N. J. A. Sloane

Other names are the Rudin-Shapiro or Golay-Rudin-Shapiro infinite word.
The Shapiro polynomials are defined by P_0 = Q_0 = 1; for n>=0, P_{n+1} = P_n + x^(2^n)*Q_n, Q_{n+1} = P_n - x^(2^n)*Q_n. Then P_n = Sum_{m=0..2^n-1} a(m)*x^m, where the a(m) (the present sequence) do not depend on n. - N. J. A. Sloane, Aug 12 2016
Related to paper-folding sequences - see the Mendès France and Tenenbaum article.
a(A022155(n)) = -1; a(A203463(n)) = 1. - Reinhard Zumkeller, Jan 02 2012
a(n) = 1 if and only if the numbers of 1's and runs of 1's in binary representation of n have the same parity: A010060(n) = A268411(n); otherwise, when A010060(n) = 1 - A268411(n), a(n) = -1. - Vladimir Shevelev, Feb 10 2016. Typo corrected and comment edited by Antti Karttunen, Jul 11 2017
A word that is uniform primitive morphic, but not pure morphic. - N. J. A. Sloane, Jul 14 2018
Named after the Austrian-American mathematician Walter Rudin (1921-2010), the mathematician Harold S. Shapiro (1928-2021) and the Swiss mathematician and physicist Marcel Jules Edouard Golay (1902-1989). - Amiram Eldar, Jun 13 2021

Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 78 and many other pages.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche, Lecture notes on automatic sequences, Krakow October 2013.
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017
Jean-Paul Allouche and M. Mendes France, Automata and Automatic Sequences, 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.
Jean-Paul Allouche and M. Mendes France, Automata and Automatic Sequences, 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]
Jean-Paul Allouche and Jonathan Sondow, Summation of rational series twisted by strongly B-multiplicative coefficients, arXiv:1408.5770 [math.NT], 2014; Electron. J. Combin., 22 #1 (2015) P1.59; see pp.9-10.
Joerg Arndt, Matters Computational (The Fxtbook), section 1.16.5 "The Golay-Rudin-Shapiro sequence", pp.44-45
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
John Brillhart and L. Carlitz, Note on the Shapiro polynomials, Proc. Amer. Math. Soc., Vol. 25 (1970), pp. 114-118.
John Brillhart and Patrick Morton, Über Summen von Rudin-Shapiroschen Koeffizienten, (German) Illinois J. Math., Vol. 22, No. 1 (1978), pp. 126-148. MR0476686 (57 #16245). - From _N. J. A. Sloane_, Jun 06 2012
John Brillhart and Patrick Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, Vol. 103 (1996) pp. 854-869.
James D. Currie, Narad Rampersad, Kalle Saari, and Luca Q. Zamboni, Extremal words in morphic subshifts, arXiv:1301.4972 [math.CO], 2013.
James D. Currie, Narad Rampersad, Kalle Saari, and Luca Q. Zamboni, Extremal words in morphic subshifts, Discrete Math., Vol. 322 (2014), pp. 53-60. MR3164037. See Sect. 8.
Michel Dekking, Michel Mendes France and Alf van der Poorten, Folds, The Mathematical Intelligencer, Vol. 4, No. 3 (1982), pp. 130-138.
Michel Dekking, Michel Mendes France and Alf van der Poorten, Folds II. Symmetry disturbed, The Mathematical Intelligencer, Vol. 4, No. 4 (1982), pp. 173-181.
Arturas Dubickas, Heights of squares of Littlewood polynomials and infinite series, Ann. Polon. Math., Vol. 105 (2012), pp. 145-163. - From _N. J. A. Sloane_, Dec 16 2012
Russell Jay Hendel, A Family of Sequences Generalizing the Thue Morse and Rudin Shapiro Sequences, arXiv:2505.20547 [cs.FL], 2025. See p. 2.
Albertus Hof, Oliver Knill and Barry Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys., Vol. 174, No. 1 (1995), pp. 149-159.
Philip Lafrance, Narad Rampersad and Randy Yee, Some properties of a Rudin-Shapiro-like sequence, arXiv:1408.2277 [math.CO], 2014.
D. H. Lehmer and Emma Lehmer, Picturesque exponential sums. II, Journal für die reine und angewandte Mathematik, Vol. 318 (1980), pp. 1-19.
Michel Mendès France and Gérald Tenenbaum, Dimension des courbes planes, papiers pliés et suites de Rudin-Shapiro. (French) Bull. Soc. Math. France, Vol. 109, No. 2 (1981), pp. 207-215. MR0623789 (82k:10073).
Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics, Vol. 23, No. 1 (2016), #P1.25.
Harold S. Shapiro, Extremal problems for polynomials and power series, Ph.D. Diss. Massachusetts Institute of Technology, 1952.
Vladimir Shevelev, Two analogs of Thue-Morse sequence, arXiv:1603.04434 [math.NT], 2016.
Eric Weisstein's World of Mathematics, Rudin-Shapiro Sequence.

Cf. A022155, A005943 (factor complexity), A014081.
Cf. A020987 (0-1 version), A020986 (partial sums), A203531 (run lengths), A033999, A380667 (first differences).
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.

a020985 n = a020985_list !! n
a020985_list = 1 : 1 : f (tail a020985_list) (-1) where
   f (x:xs) w = x : x*w : f xs (0 - w)
-- Reinhard Zumkeller, Jan 02 2012

A020985 := proc(n) option remember; if n = 0 then 1 elif n mod 2 = 0 then A020985(n/2) else (-1)^((n-1)/2 )*A020985( (n-1)/2 ); fi; end;

a[0] = 1; a[1] = 1; a[n_?EvenQ] := a[n] = a[n/2]; a[n_?OddQ] := a[n] = (-1)^((n-1)/2)* a[(n-1)/2]; a /@ Range[0, 80] (* Jean-François Alcover, Jul 05 2011 *)
a[n_] := 1 - 2 Mod[Length[FixedPointList[BitAnd[#, # - 1] &, BitAnd[n, Quotient[n, 2]]]], 2] (* Jan Mangaldan, Jul 23 2015 *)
Array[RudinShapiro, 81, 0] (* JungHwan Min, Dec 22 2016 *)

A020985(n)=(-1)^A014081(n)  \\ M. F. Hasler, Jun 06 2012

def a014081(n): return sum([((n>>i)&3==3) for i in range(len(bin(n)[2:]) - 1)])
def a(n): return (-1)**a014081(n) # Indranil Ghosh, Jun 03 2017

def A020985(n): return -1 if (n&(n>>1)).bit_count()&1 else 1 # Chai Wah Wu, Feb 11 2023

a(0) = a(1) = 1; thereafter, a(2n) = a(n), a(2n+1) = a(n) * (-1)^n. [Brillhart and Carlitz, in proof of theorem 4]
a(0) = a(1) = 1, a(2n) = a(n), a(2n+1) = a(n)*(1-2*(n AND 1)), where AND is the bitwise AND operator. - Alex Ratushnyak, May 13 2012
Brillhart and Morton (1978) list many properties.
a(n) = (-1)^A014081(n)  = (-1)^A020987(n) = 1-2*A020987(n). - M. F. Hasler, Jun 06 2012
Sum_{n >= 1} a(n-1)*(8*n^2+4*n+1)/(2*n*(2*n+1)*(4*n+1)) = 1; see Allouche and Sondow, 2015. - Jean-Paul Allouche and Jonathan Sondow, Mar 21 2015

A071053 Number of ON cells at n-th generation of 1-D CA defined by Rule 150, starting with a single ON cell at generation 0.

Original entry on oeis.org

1, 3, 3, 5, 3, 9, 5, 11, 3, 9, 9, 15, 5, 15, 11, 21, 3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27

Offset: 0

Hans Havermann, May 26 2002

Number of 1's in n-th row of triangle in A071036.
Number of odd coefficients in (x^2+x+1)^n. - Benoit Cloitre, Sep 05 2003. This result was given in Wolfram (1983). - N. J. A. Sloane, Feb 17 2015
This is also the odd-rule cellular automaton defined by OddRule 007 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
This is the Run Length Transform of S(n) = Jacobsthal(n+2) (cf. A001045). The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - N. J. A. Sloane, Sep 05 2014

			May be arranged into blocks of sizes 1,1,2,4,8,16,...:
1,
3,
3, 5,
3, 9, 5, 11,
3, 9, 9, 15, 5, 15, 11, 21,
3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, ...
... - _N. J. A. Sloane_, Sep 05 2014
.
From _Omar E. Pol_, Mar 15 2015: (Start)
Apart from the initial 1, the sequence can be written also as an irregular tetrahedron T(s,r,k) = A001045(r+2) * a(k), s>=1, 1<=r<=s, 0<=k<=(A011782(s-r)-1) as shown below (see also _Joerg Arndt_'s equivalent program):
3;
..
3;
5;
.......
3,   9;
5;
11;
...............
3,   9,  9, 15;
5,  15;
11;
21;
...............................
3,   9,  9, 15,  9, 27, 15, 33;
5,  15, 15, 25;
11, 33;
21;
43;
..............................................................
3,   9,  9, 15,  9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63;
5,  15, 15, 25, 15, 45, 25, 55;
11, 33, 33, 55;
21, 63;
43;
85;
...
Note that every row r is equal to A001045(r+2) times the beginning of the sequence itself, thus in 3D every column contains the same number.
(End)

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

N. J. A. Sloane, Table of n, a(n) for n = 0..16383 (first 1024 terms from T. D. Noe)
Joerg Arndt, A071053 (number of odd terms in expansion of (1+x+x^2)^n), SeqFan Mailing List, Mar 09 2015.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.
Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Janko Gravner and Alexander E. Holroyd, Percolation and Disorder-Resistance in Cellular Automata, Annals of Probability, volume 43, number 4, 2015, pages 1731-1776. Also arxiv:1304.7301 [math.PR], 2013-2015 and second author's copy. See Fig. 1.1 (left).
S. Kropf, S. Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
N. Pitsianis, P. Tsalides, G. L. Bleris, A. Thanailakis & H. C. Card, Deterministic one-dimensional cellular automata, Journal of Statistical Physics, 56(1-2), 99-112, 1989. [Discusses Rule 150]
T. Sillke and Helmut Postl, Odd trinomials: t(n) = (1+x+x^2)^n
T. Sillke and Helmut Postl, Odd trinomials: t(n) = (1+x+x^2)^n [Cached copy, with permission]
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
S. Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55 (1983), 601--644.
Index entries for sequences related to cellular automata

Cf. A038184, A118110, A071036, A001045, A253102, A020987, A246035, A245562, A087206.

a[n_] := Total[CoefficientList[(x^2 + x + 1)^n, x, Modulus -> 2]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Aug 05 2018 *)

b(n) = { (2^n - (-1)^n) / 3; }  \\ A001045
a(n)=
{
    if ( n==0, return(1) );
    \\ Use  a( 2^k * t ) = a(t)
    n \= 2^valuation(n,2);
    if ( n==1, return(3) );  \\ Use a(2^k) == 3
    \\ now n is odd
    my ( v1 = valuation(n+1, 2) );
    \\ Use a( 2^k - 1 ) = A001045( 2 + k ):
    if ( n == 2^v1 - 1 ,  return( b( v1 + 2 ) ) );
    my( k2 = 1, k = 0 );
    while ( k2 < n,  k2 <<= 1; k+=1 );
    if ( k2 > n, k2 >>= 1; k-=1 );
    my( t = n - k2 );
    \\ here  n == 2^k + 1 where k maximal
    \\ Use the following:
    \\ a( 2^k + t ) =  3 * a(t)  if  t <= 2^(k-1)
    \\ a( 2^k + 2^(k-1) + t ) =  5 * a(t)  if  t <= 2^(k-2)
    \\ a( 2^k + 2^(k-1) + 2^(k-2) + t ) =  11* a(t)  if  t <= 2^(k-3)
    \\  ... etc. ...
    \\ a( 2^k + ... + 2^(k-s) + t ) = A001045(s+2) * a(t)  if  t <= 2^((k-1)-s)
    my ( s=1 );
    while ( 1 ,
        k2 >>= 1;
        if ( t <= k2 ,  return(  b(s+2) * a(t) ) );
        t -= k2;
        s += 1;
    );
}
\\ Joerg Arndt, Mar 15 2015, from SeqFan Mailing List, Mar 09 2015

a(n) = Product_{i in row n of A245562} A001045(i+2) [Sillke]. For example, a(11) = A001045(3)*A001045(4) = 3*5 = 15. - N. J. A. Sloane, Aug 10 2014
Floor((a(n)-1)/4) mod 2 = A020987(n). - Ralf Stephan, Mar 18 2004
a(2*n) = a(n); a(2*n+1) = a(n) + 2*a(floor(n/2)). - Peter J. Taylor, Mar 26 2020
Sum_{k = 0..2^n-1} a(k) = A087206(n). - Linhua Zou, Jun 13 2025

Entry revised by N. J. A. Sloane, Aug 13 2014

Terms a(0)..a(13) were verified and terms a(14)..a(32) were computed using the first 2^32 terms of the GRS sequence. - Joerg Arndt, Jun 10 2012

Terms a(0)..a(63) were computed using the first 2^36 terms of the GRS sequence, and are consistent with Arndt's conjectured g.f. - Sean A. Irvine, Oct 12 2016

Also, if prefixed by 0, the trajectory of 0 under repeated applications of the morphism 0 -> 0,1, 1 -> 1,2, 2 -> 2,2. This is a word that is pure uniform morphic, but neither primitive morphic nor recurrent. - N. J. A. Sloane, Jul 15 2018

The arithmetic mean (1/(n+1))*Sum_{k=0..n} a(k) converges to Pi. What is effectively the same: the Cesaro limit (C1) of a(n) is Pi. - Hieronymus Fischer, Jan 31 2006

A word that is uniformly recurrent, but not morphic. - N. J. A. Sloane, Jul 14 2018

cp's OEIS Frontend

A005943 Factor complexity (number of subwords of length n) of the Golay-Rudin-Shapiro binary word A020987.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A380593 Starting position of the first occurrence of the longest monochromatic arithmetic progression of difference n in the Rudin-Shapiro sequence (A020987).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Walnut

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

R

Formula

A003849 The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A030302 Write n in base 2 and juxtapose; irregular table in which row n lists the binary expansion of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

A063438 a(n) = floor((n+1)Pi) - floor(nPi).