A001285 -id:A001285 - 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)

A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.

Original entry on oeis.org

0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60, 63, 65, 66, 68, 71, 72, 75, 77, 78, 80, 83, 85, 86, 89, 90, 92, 95, 96, 99, 101, 102, 105, 106, 108, 111, 113, 114, 116, 119, 120, 123, 125, 126, 129

Offset: 1

N. J. A. Sloane

This sequence and A000069 give the unique solution to the problem of splitting the nonnegative integers into two classes in such a way that sums of pairs of distinct elements from either class occur with the same multiplicities [Lambek and Moser]. Cf. A000028, A000379.
In French: les nombres païens.
Theorem: First differences give A036585. (Observed by Franklin T. Adams-Watters.)
Proof from Max Alekseyev, Aug 30 2006 (edited by N. J. A. Sloane, Jan 05 2021): (Start)
Observe that if the last bit of a(n) is deleted, we get the nonnegative numbers 0, 1, 2, 3, ... in order.
The last bit in a(n+1) is 1 iff the number of bits in n is odd, that is, iff A010060(n+1) is 1.
So, taking into account the different offsets here and in A010060, we have a(n) = 2*(n-1) + A010060(n-1).
Therefore the first differences of the present sequence equal 2 + first differences of A010060, which equals A036585.  QED (End)
Integers k such that A010060(k-1)=0. - Benoit Cloitre, Nov 15 2003
Indices of zeros in the Thue-Morse sequence A010060 shifted by 1. - Tanya Khovanova, Feb 13 2009
Conjecture, checked up to 10^6: a(n) is also the sequence of numbers k representable as k = ror(x) XOR rol(x) (for some integer x) where ror(x)=A038572(x) is x rotated one binary place to the right, rol(x)=A006257(x) is x rotated one binary place to the left, and XOR is the binary exclusive-or operator. - Alex Ratushnyak, May 14 2016
From Charlie Neder, Oct 07 2018: (Start)
Conjecture is true: ror(x) and rol(x) have an even number of 1 bits in total (= 2 * A000120(x)), and XOR preserves the parity of this total, so the resulting number must have an even number of 1 bits. An x can be constructed corresponding to a(n) like so:
If the number of bits in a(n) is even, add a leading 0 so a(n) is 2k+1 bits long.
Do an inverse shuffle on a(n), then "divide" by 11, rotate the result k bits to the right, and shuffle to get x. (End)
Numbers of the form m XOR (2*m) for some m >= 0. - Rémy Sigrist, Feb 07 2021
The terms "evil numbers" and "odious numbers" were coined by Richard K. Guy, c. 1976 (Haque and Shallit, 2016) and appeared in the book by Berlekamp et al. (Vol. 1, 1st ed., 1982). - Amiram Eldar, Jun 08 2021

Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, 2nd ed., A K Peters, 2001, chapter 14, p. 110.
Hugh L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
Donald J. Newman, A Problem Seminar, Springer; see Problem #89.
Vladimir S. Shevelev, On some identities connected with the partition of the positive integers with respect to the Morse sequence, Izv. Vuzov of the North-Caucasus region, Nature sciences 4 (1997), 21-23 (Russian).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche and Henri Cohen, Dirichlet series and curious infinite products, Bull. London Math. Soc., Vol. 17 (1985), pp. 531-538.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197; DOI.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, Aequationes mathematicae, Vol. 90 (2016), pp. 341-353; alternative link.
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 19.
Chris Bernhardt, Evil twins alternate with odious twins, Math. Mag., Vol. 82, No. 1 (2009), pp. 57-62; alternative link.
Joshua N. Cooper, Dennis Eichhorn and Kevin O'Bryant, Reciprocals of binary power series, International Journal of Number Theory, Vol. 2, No. 4 (2006), pp. 499-522; arXiv preprint, arXiv:math/0506496 [math.NT], 2005.
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math., Vol. 312, No. 1 (2012), pp. 42-46.
E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presque premiers, (French) [Sums of digits and almost primes] Math. Ann., Vol. 305, No. 3 (1996), pp. 571-599. MR1397437 (97k:11029)
Sajed Haque, Chapter 3.2 of Discriminators of Integer Sequences, thesis, University of Waterloo, Ontario, Canada, 2017. See p. 38.
Sajed Haque and Jeffrey Shallit, Discriminators and k-Regular Sequences Integers, Vol. 16 (2016), Article A76; arXiv preprint, arXiv:1605.00092 [cs.DM], 2016.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
J. Lambek and L. Moser, On some two way classifications of integers, Canad. Math. Bull., Vol. 2, No. 2 (1959), pp. 85-89.
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., Vol. 3, No. 4 (1974), pp. 255-261.
Jeffrey O. Shallit, On infinite products associated with sums of digits, J. Number Theory, Vol. 21, No. 2 (1985), pp. 128-134.
Jeffrey Shallit, Frobenius Numbers and Automatic Sequences, arXiv:2103.10904 [math.NT], 2021.
Jeffrey Shallit, Additive Number Theory via Automata and Logic, arXiv:2112.13627 [math.NT], 2021.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, arXiv preprint arXiv:1207.0404 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 17 2012
Vladimir Shevelev and Peter J. C. Moses, A family of digit functions with large periods, arXiv preprint arXiv:1209.5705 [math.NT], 2012.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, INTEGERS, Vol. 14 (2014) #64.
Eric Weisstein's World of Mathematics, Evil Number.
Index entries for sequences related to binary expansion of n
Index entries for "core" sequences

Complement of A000069 (the odious numbers). Cf. A133009.
a(n)=2*n+A010060(n)=A000069(n)-(-1)^A010060(n). Cf. A018900.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
Cf. A036585 (differences), A010060, A006364.
For primes see A027699, also A130593.
Cf. A006068, A048724, A059010, A094677.

a001969 n = a001969_list !! (n-1)
a001969_list = [x | x <- [0..], even $ a000120 x]
-- Reinhard Zumkeller, Feb 01 2012

[ n : n in [0..129] | IsEven(&+Intseq(n,2)) ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

s := proc(n) local i,j,ans; ans := [ ]; j := 0; for i from 0 while jA001969 := n->t1[n]; # s(k) gives first k terms.
# Alternative:
seq(`if`(add(k, k=convert(n,base,2))::even, n, NULL), n=0..129); # Peter Luschny, Jan 15 2021
# alternative for use outside this sequence
isA001969 := proc(n)
    add(d,d=convert(n,base,2)) ;
    type(%,'even') ;
end proc:
A001969 := proc(n)
    option remember ;
    local a;
    if n = 0 then
        1;
    else
        for a from procname(n-1)+1 do
            if isA001969(a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A001969(n),n=1..200) ; # R. J. Mathar, Aug 07 2022

Select[Range[0,300], EvenQ[DigitCount[ #, 2][[1]]] &]
a[ n_] := If[ n < 1, 0, With[{m = n - 1}, 2 m + Mod[-Total@IntegerDigits[m, 2], 2]]]; (* Michael Somos, Jun 09 2019 *)

a(n)=n-=1; 2*n+subst(Pol(binary(n)),x,1)%2

a(n)=if(n<1,0,if(n%2==0,a(n/2)+n,-a((n-1)/2)+3*n))

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

def ok(n): return bin(n)[2:].count('1') % 2 == 0
print(list(filter(ok, range(130)))) # Michael S. Branicky, Jun 02 2021

from itertools import chain, count, islice
def A001969_gen(): # generator of terms
    return chain((0,),chain.from_iterable((sorted(n^ n<<1 for n in range(2**l,2**(l+1))) for l in count(0))))
A001969_list = list(islice(A001969_gen(),30)) # Chai Wah Wu, Jun 29 2022

def A001969(n): return ((m:=n-1).bit_count()&1)+(m<<1) # Chai Wah Wu, Mar 03 2023

a(n+1) - A001285(n) = 2n-1 has been verified for n <= 400. - John W. Layman, May 16 2003 [This can be directly verified by comparing Ralf Stephan's formulas for this sequence (see below) and for A001285. - Jianing Song, Nov 04 2024]
Note that 2n+1 is in the sequence iff 2n is not and so this sequence has asymptotic density 1/2. - Franklin T. Adams-Watters, Aug 23 2006
a(n) = (1/2) * (4n - 3 - (-1)^A000120(n-1)). - Ralf Stephan, Sep 14 2003
G.f.: Sum_{k>=0} (t(3+2t+3t^2)/(1-t^2)^2) * Product_{l=0..k-1} (1-x^(2^l)), where t = x^2^k. - Ralf Stephan, Mar 25 2004
a(2*n+1) + a(2*n) = A017101(n-1) = 8*n-5.
a(2*n) - a(2*n-1) gives the Thue-Morse sequence (3, 1 version): 3, 1, 1, 3, 1, 3, 3, 1, 1, 3, .... A001969(n) + A000069(n) = A016813(n-1) = 4*n-3. - Philippe Deléham, Feb 04 2004
a(1) = 0; for n > 1: a(n) = 3*n-3 - a(n/2) if n even, a(n) = a((n+1)/2)+n-1 if n odd.
Let b(n) = 1 if sum of digits of n is even, -1 if it is odd; then Shallit (1985) showed that Product_{n>=0} ((2n+1)/(2n+2))^b(n) = 1/sqrt(2).
a(n) = 2n - 2 + A010060(n-1). - Franklin T. Adams-Watters, Aug 28 2006
A005590(a(n-1)) <= 0. - Reinhard Zumkeller, Apr 11 2012
A106400(a(n-1)) = 1. - Reinhard Zumkeller, Apr 29 2012
a(n) = (a(n-1) + 2) XOR A010060(a(n-1) + 2). - Falk Hüffner, Jan 21 2022
a(n+1) = A006068(n) XOR (2*A006068(n)). - Rémy Sigrist, Apr 14 2022

More terms from Robin Trew (trew(AT)hcs.harvard.edu)

A001316 Gould's sequence: a(n) = Sum_{k=0..n} (binomial(n,k) mod 2); number of odd entries in row n of Pascal's triangle (A007318); a(n) = 2^A000120(n).

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32, 8, 16, 16, 32, 16, 32, 32, 64, 2, 4, 4, 8, 4, 8, 8, 16, 4, 8, 8, 16, 8, 16, 16, 32, 4, 8, 8, 16, 8, 16, 16, 32

Offset: 0

N. J. A. Sloane

Also called Dress's sequence.
This sequence might be better called Glaisher's sequence, since James Glaisher showed that odd binomial coefficients are counted by 2^A000120(n) in 1899. - Eric Rowland, Mar 17 2017 [However, the name "Gould's sequence" is deeply entrenched in the literature. - N. J. A. Sloane, Mar 17 2017] [Named after the American mathematician Henry Wadsworth Gould (b. 1928). - Amiram Eldar, Jun 19 2021]
All terms are powers of 2. The first occurrence of 2^k is at n = 2^k - 1; e.g., the first occurrence of 16 is at n = 15. - Robert G. Wilson v, Dec 06 2000
a(n) is the highest power of 2 dividing binomial(2n,n) = A000984(n). - Benoit Cloitre, Jan 23 2002
Also number of 1's in n-th row of triangle in A070886. - Hans Havermann, May 26 2002. Equivalently, number of live cells in generation n of a one-dimensional cellular automaton, Rule 90, starting with a single live cell. - Ben Branman, Feb 28 2009. Ditto for Rule 18. - N. J. A. Sloane, Aug 09 2014. This is also the odd-rule cellular automaton defined by OddRule 003 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
Also number of numbers k, 0<=k<=n, such that (k OR n) = n (bitwise logical OR): a(n) = #{k : T(n,k)=n, 0<=k<=n}, where T is defined as in A080098. - Reinhard Zumkeller, Jan 28 2003
To construct the sequence, start with 1 and use the rule: If k >= 0 and a(0),a(1),...,a(2^k-1) are the first 2^k terms, then the next 2^k terms are 2*a(0),2*a(1),...,2*a(2^k-1). - Benoit Cloitre, Jan 30 2003
Also, numerator((2^k)/k!). - Mohammed Bouayoun (mohammed.bouayoun(AT)sanef.com), Mar 03 2004
The odd entries in Pascal's triangle form the Sierpiński Gasket (a fractal). - Amarnath Murthy, Nov 20 2004
Row sums of Sierpiński's Gasket A047999. - Johannes W. Meijer, Jun 05 2011
Fixed point of the morphism "1" -> "1,2", "2" -> "2,4", "4" -> "4,8", ..., "2^k" -> "2^k,2^(k+1)", ... starting with a(0) = 1; 1 -> 12 -> 1224 -> = 12242448 -> 122424482448488(16) -> ... . - Philippe Deléham, Jun 18 2005
a(n) = number of 1's of stage n of the one-dimensional cellular automaton with Rule 90. - Andras Erszegi (erszegi.andras(AT)chello.hu), Apr 01 2006
a(33)..a(63) = A117973(1)..A117973(31). - Stephen Crowley, Mar 21 2007
Or the number of solutions of the equation: A000120(x) + A000120(n-x) = A000120(n). - Vladimir Shevelev, Jul 19 2009
For positive n, a(n) equals the denominator of the permanent of the n X n matrix consisting entirely of (1/2)'s. - John M. Campbell, May 26 2011
Companions to A001316 are A048896, A105321, A117973, A151930 and A191488. They all have the same structure. We observe that for all these sequences a((2*n+1)*2^p-1) = C(p)*A001316(n), p >= 0. If C(p) = 2^p then a(n) = A001316(n), if C(p) = 1 then a(n) = A048896(n), if C(p) = 2^p+2 then a(n) = A105321(n+1), if C(p) = 2^(p+1) then a(n) = A117973(n), if C(p) = 2^p-2 then a(n) = (-1)*A151930(n) and if C(p) = 2^(p+1)+2 then a(n) = A191488(n). Furthermore for all a(2^p - 1) = C(p). - Johannes W. Meijer, Jun 05 2011
a(n) = number of zeros in n-th row of A219463 = number of ones in n-th row of A047999. - Reinhard Zumkeller, Nov 30 2012
This is the Run Length Transform of S(n) = {1,2,4,8,16,...} (cf. A000079). 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
A105321(n+1) = a(n+1) + a(n). - Reinhard Zumkeller, Nov 14 2014
a(n) = A261363(n,n) = number of distinct terms in row n of A261363 = number of odd terms in row n+1 of A261363. - Reinhard Zumkeller, Aug 16 2015
From Gary W. Adamson, Aug 26 2016: (Start)
A production matrix for the sequence is lim_{k->infinity} M^k, the left-shifted vector of M:
  1, 0, 0, 0, 0, ...
  2, 0, 0, 0, 0, ...
  0, 1, 0, 0, 0, ...
  0, 2, 0, 0, 0, ...
  0, 0, 1, 0, 0, ...
  0, 0, 2, 0, 0, ...
  0, 0, 0, 1, 0, ...
  ...
The result is equivalent to the g.f. of Apr 06 2003: Product_{k>=0} (1 + 2*z^(2^k)). (End)
Number of binary palindromes of length n for which the first floor(n/2) symbols are themselves a palindrome (Ji and Wilf 2008). - Jeffrey Shallit, Jun 15 2017

			Has a natural structure as a triangle:
  1,
  2,
  2,4,
  2,4,4,8,
  2,4,4,8,4,8,8,16,
  2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,
  2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,32,64,
  ...
The rows converge to A117973.
From _Omar E. Pol_, Jun 07 2009: (Start)
Also, triangle begins:
   1;
   2,2;
   4,2,4,4;
   8,2,4,4,8,4,8,8;
  16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16;
  32,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,32;
  64,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,4,8,8,16,8,16,16,32,8,16,16,32,16,32,...
(End)
G.f. = 1 + 2*x + 2*x^2 + 4*x^3 + 2*x^4 + 4*x^5 + 4*x^6 + 8*x^7 + 2*x^8 + ... - _Michael Somos_, Aug 26 2015

Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, p. 75ff.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 145-151.
James W. L. Glaisher, On the residue of a binomial-theorem coefficient with respect to a prime modulus, Quarterly Journal of Pure and Applied Mathematics, Vol. 30 (1899), pp. 150-156.
H. W. Gould, Exponential Binomial Coefficient Series. Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sep 1961.
Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram, Algebraic properties of cellular automata, Comm. Math. Physics, Vol. 93 (1984), pp. 219-258. Reprinted in Theory and Applications of Cellular Automata, S Wolfram, Ed., World Scientific, 1986, pp. 51-90 and in Cellular Automata and Complexity: Collected Papers of Stephen Wolfram, Addison-Wesley, 1994, pp. 71-113
Manfred R. Schroeder, Fractals, Chaos, Power Laws, W. H. Freeman, NY, 1991, page 383.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Andrew Wuensche, Exploring Discrete Dynamics, Luniver Press, 2011. See Fig. 2.3.

Indranil Ghosh, Table of n, a(n) for n = 0..50000 (terms 0..1000 from T. D. Noe)
David Applegate, Omar E. Pol, and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), pp. 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
George Beck and Karl Dilcher, A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence, arXiv:2106.10400 [math.CO], 2021.
Christina Talar Bekaroğlu, Analyzing Dynamics of Larger than Life: Impacts of Rule Parameters on the Evolution of a Bug's Geometry, Master's thesis, Calif. State Univ. Northridge (2023). See pp. 91-92.
Neil J. Calkin, Eunice Y. S. Chan, and Robert M. Corless, Some Facts and Conjectures about Mandelbrot Polynomials, Maple Transactions (2021) Vol. 1, No. 1, Article 1.
Neil J. Calkin, Eunice Y. S. Chan, Robert M. Corless, David J. Jeffrey, and Piers W. Lawrence, A Fractal Eigenvector, arXiv:2104.01116 [math.DS], 2021.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory, Vol. 117 (2006), pp. 191-215.
Philippe Dumas, Diviser pour régner Comportement asymptotique.
Philippe Dumas, Diviser pour régner Comportement asymptotique. (has many references)
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.
Steven R. Finch, Stolarsky-Harborth Constant. [Broken link]
Steven R. Finch, Stolarsky-Harborth Constant. [From the Wayback machine]
Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, Picturesque convolution-like recurrences and partial sums' generation, arXiv:2507.23619 [math.NT], 2025. See p. 28.
Michael Gilleland, Some Self-Similar Integer Sequences.
Po-Yi Huang and Wen-Fong Ke, Sequences Derived from The Symmetric Powers of {1, 2, ..., k}, arXiv:2307.07733 [math.CO], 2023.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Periodic minimum in the count of binomial coefficients not divisible by a prime, arXiv:2408.06817 [math.NT], 2024.
Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes, Amer. Math. Monthly, Vol. 115, No. 5 (2008), pp. 447-451.
Alan J. Macfarlane, Generating functions for integer sequences defined by the evolution of cellular automata....
Hans Montanus and Ron Westdijk, Cellular Automation and Binomials, Green Blue Mathematics (2022), p. 57.
Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117, No. 7 (2010), pp. 581-598.
Tomaz Pisanski and Thomas W. Tucker, Growth in Repeated Truncations of Maps, Atti Sem. Mat. Fis. Univ. Modena, Vol. 49 (2001), suppl., pp. 167-176.
David G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag., Vol. 67, No. 5 (1994), pp. 323-344.
Joseph M. Shunia, A Polynomial Ring Connecting Central Binomial Coefficients and Gould's Sequence, arXiv:2312.00302 [math.GM], 2023.
N. J. A. Sloane, Illustration of first 20 generations of Rule 90.
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS.
Lukas Spiegelhofer and Michael Wallner, Divisibility of binomial coefficients by powers of two, arXiv:1710.10884 [math.NT], 2017.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Alexander Yu. Vlasov, Modelling reliability of reversible circuits with 2D second-order cellular automata, arXiv:2312.13034 [nlin.CG], 2023. See page 12.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.
Stephen Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., Vol. 55 (1983), pp. 601-644.
Stephen Wolfram, Geometry of Binomial Coefficients, Amer. Math. Monthly, Vol. 91, No. 9 (November 1984), pp. 566-571.
Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv preprint arXiv:1610.06166 [math.CO], 2016.
Zhujun Zhang, A Note on Counting Binomial Heaps, ResearchGate (2019).
Index entries for sequences related to cellular automata
Index entries for sequences that are fixed points of mappings
Index entries for sequences computed with run length transform

Equals left border of triangle A166548. - Gary W. Adamson, Oct 16 2009
For generating functions Product_{k>=0} (1+a*x^(b^k)) for the following values of (a,b) see: (1,2) A000012 and A000027, (1,3) A039966 and A005836, (1,4) A151666 and A000695, (1,5) A151667 and A033042, (2,2) A001316, (2,3) A151668, (2,4) A151669, (2,5) A151670, (3,2) A048883, (3,3) A117940, (3,4) A151665, (3,5) A151671, (4,2) A102376, (4,3) A151672, (4,4) A151673, (4,5) A151674.
For partial sums see A006046. For first differences see A151930.
This is the numerator of 2^n/n!, while A049606 gives the denominator.
Cf. A051638, A048967, A007318, A094959, A048896, A117973, A008977, A139541, A048883, A102376, A038573, A159913, A000079, A166548, A006047, A089898, A105321, A061142.
Cf. A047999, A261363, A261366.
If we subtract 1 from the terms we get a pair of essentially identical sequences, A038573 and A159913.
A163000 and A163577 count binomial coefficients with 2-adic valuation 1 and 2. A275012 gives a measure of complexity of these sequences. - Eric Rowland, Mar 15 2017
Cf. A286575 (run-length transform), A368655 (binomial transform), also A037445.

import Data.List (transpose)
a001316 = sum . a047999_row  -- Reinhard Zumkeller, Nov 24 2012
a001316_list = 1 : zs where
   zs = 2 : (concat $ transpose [zs, map (* 2) zs])
-- Reinhard Zumkeller, Aug 27 2014, Sep 16 2011
(Sage, Python)
from functools import cache
@cache
def A001316(n):
    if n <= 1: return n+1
    return A001316(n//2) << n%2
print([A001316(n) for n in range(88)])  # Peter Luschny, Nov 19 2012

A001316 := proc(n) local k; add(binomial(n,k) mod 2, k=0..n); end;
S:=[1]; S:=[op(S),op(2*s)]; # repeat ad infinitum!
a := n -> 2^add(i,i=convert(n,base,2)); # Peter Luschny, Mar 11 2009

Table[ Sum[ Mod[ Binomial[n, k], 2], {k, 0, n} ], {n, 0, 100} ]
Nest[ Join[#, 2#] &, {1}, 7] (* Robert G. Wilson v, Jan 24 2006 and modified Jul 27 2014 *)
Map[Function[Apply[Plus,Flatten[ #1]]], CellularAutomaton[90,{{1},0},100]] (* Produces counts of ON cells. N. J. A. Sloane, Aug 10 2009 *)
ArrayPlot[CellularAutomaton[90, {{1}, 0}, 20]] (* Illustration of first 20 generations. - N. J. A. Sloane, Aug 14 2014 *)
Table[2^(RealDigits[n - 1, 2][[1]] // Total), {n, 1, 100}] (* Gabriel C. Benamy, Dec 08 2009 *)
CoefficientList[Series[Exp[2*x], {x, 0, 100}], x] // Numerator (* Jean-François Alcover, Oct 25 2013 *)
Count[#,?OddQ]&/@Table[Binomial[n,k],{n,0,90},{k,0,n}] (* _Harvey P. Dale, Sep 22 2015 *)
2^DigitSum[Range[0, 100], 2] (* Paolo Xausa, Jul 31 2025 *)

{a(n) = if( n<0, 0, numerator(2^n / n!))};

PARI
```
A001316(n)=1<M. F. Hasler, May 03 2009
```

a(n)=2^hammingweight(n) \\ Charles R Greathouse IV, Jan 04 2013

def A001316(n):
    return 2**bin(n)[2:].count("1") # Indranil Ghosh, Feb 06 2017

def A001316(n): return 1<Karl-Heinz Hofmann, Aug 01 2025

import numpy # (version >= 2.0.0)
n_up_to = 2**22
A000079 = 1 << numpy.arange(n_up_to.bit_length())
A001316 = A000079[numpy.bitwise_count(numpy.arange(n_up_to))]
print(A001316[0:100]) # Karl-Heinz Hofmann, Aug 01 2025

(define (A001316 n) (let loop ((n n) (z 1)) (cond ((zero? n) z) ((even? n) (loop (/ n 2) z)) (else (loop (/ (- n 1) 2) (* z 2)))))) ;; Antti Karttunen, May 29 2017

a(n) = 2^A000120(n).
a(0) = 1; for n > 0, write n = 2^i + j where 0 <= j < 2^i; then a(n) = 2*a(j).
a(n) = 2*a(n-1)/A006519(n) = A000079(n)*A049606(n)/A000142(n).
a(n) = A038573(n) + 1.
G.f.: Product_{k>=0} (1+2*z^(2^k)). - Ralf Stephan, Apr 06 2003
a(n) = Sum_{i=0..2*n} (binomial(2*n, i) mod 2)*(-1)^i. - Benoit Cloitre, Nov 16 2003
a(n) mod 3 = A001285(n). - Benoit Cloitre, May 09 2004
a(n) = 2^n - 2*Sum_{k=0..n} floor(binomial(n, k)/2). - Paul Barry, Dec 24 2004
a(n) = Product_{k=0..log_2(n)} 2^b(n, k), b(n, k) = coefficient of 2^k in binary expansion of n. - Paul D. Hanna
Sum_{k=0..n-1} a(k) = A006046(n).
a(n) = n/2 + 1/2 + (1/2)*Sum_{k=0..n} (-(-1)^binomial(n,k)). - Stephen Crowley, Mar 21 2007
G.f. for a(n)/A156769(n): (1/2)*z^(1/2)*sinh(2*z^(1/2)). - Johannes W. Meijer, Feb 20 2009
Equals infinite convolution product of [1,2,0,0,0,0,0,0,0] aerated (A000079 - 1) times, i.e., [1,2,0,0,0,0,0,0,0] * [1,0,2,0,0,0,0,0,0] * [1,0,0,0,2,0,0,0,0]. - Mats Granvik, Gary W. Adamson, Oct 02 2009
a(n) = f(n, 1) with f(x, y) = if x = 0 then y otherwise f(floor(x/2), y*(1 + x mod 2)). - Reinhard Zumkeller, Nov 21 2009
a(n) = 2^(number of 1's in binary form of (n-1)). - Gabriel C. Benamy, Dec 08 2009
a((2*n+1)*2^p-1) = (2^p)*a(n), p >= 0. - Johannes W. Meijer, Jun 05 2011
a(n) = A000120(A001317(n)). - Reinhard Zumkeller, Nov 24 2012
a(n) = A226078(n,1). - Reinhard Zumkeller, May 25 2013
a(n) = lcm(n!, 2^n) / n!. - Daniel Suteu, Apr 28 2017
a(n) = A061142(A005940(1+n)). - Antti Karttunen, May 29 2017
a(0) = 1, a(2*n) = a(n), a(2*n+1) = 2*a(n). - Daniele Parisse, Feb 15 2024
a(n*m) <= a(n)^A000120(m). - Joe Amos, Mar 27 2025

Additional comments from Henry Bottomley, Mar 12 2001

Further comments from N. J. A. Sloane, May 30 2009

A003159 Numbers whose binary representation ends in an even number of zeros.

Original entry on oeis.org

1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 25, 27, 28, 29, 31, 33, 35, 36, 37, 39, 41, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 57, 59, 60, 61, 63, 64, 65, 67, 68, 69, 71, 73, 75, 76, 77, 79, 80, 81, 83, 84, 85, 87, 89, 91, 92, 93, 95, 97, 99, 100, 101, 103, 105

Offset: 1

N. J. A. Sloane, Simon Plouffe

Fraenkel (2010) called these the "vile" numbers.
Minimal with respect to property that parity of number of 1's in binary expansion alternates.
Minimal with respect to property that sequence is half its complement. [Corrected by Aviezri S. Fraenkel, Jan 29 2010]
If k appears then 2k does not.
Increasing sequence of positive integers k such that A035263(k)=1 (from paper by Allouche et al.). - Emeric Deutsch, Jan 15 2003
a(n) is an odious number (see A000069) for n odd; a(n) is an evil number (see A001969) for n even. - Philippe Deléham, Mar 16 2004
Indices of odd numbers in A007913, in A001511. - Philippe Deléham, Mar 27 2004
Partial sums of A026465. - Paul Barry, Dec 09 2004
A121701(2*a(n)) = A121701(a(n)); A096268(a(n)-1) = 0. - Reinhard Zumkeller, Aug 16 2006
A different permutation of the same terms may be found in A141290 and the accompanying array. - Gary W. Adamson, Jun 14 2008
a(n) = n-th clockwise Tower of Hanoi move; counterclockwise if not in the sequence. - Gary W. Adamson, Jun 14 2008
Indices of terms of Thue-Morse sequence A010060 which are different from the previous term. - Tanya Khovanova, Jan 06 2009
The sequence has the following fractal property. Remove the odd numbers from the sequence, leaving 4,12,16,20,28,36,44,48,52,... Dividing these terms by 4 we get 1,3,4,5,7,9,11,12,..., which is the original sequence back again. - Benoit Cloitre, Apr 06 2010
From Gary W. Adamson, Mar 21 2010: (Start)
A conjectured identity relating to the partition sequence, A000041 as polcoeff p(x); A003159, and its characteristic function A035263: (1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ...); and A036554 indicating n-th terms with zeros in A035263: (2, 6, 8, 10, 14, 18, 22, ...).
The conjecture states that p(x) = A(x) = A(x^2) when A(x) = polcoeff A174065 = the Euler transform of A035263 = 1/((1-x)*(1-x^3)*(1-x^4)*(1-x^5)*...) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + ... and the aerated variant = the Euler transform of the complement of A035263: 1/((1-x^2)*(1-x^6)*(1-x^8)*...) = 1 + x^2 + x^4 + 2*x^6 + 3*x^8 + 4*x^10 + ....
(End)
The conjecture above was proved by Jean-Paul Allouche on Dec 21 2013. - Gary W. Adamson, Jan 22 2014
If the lower s-Wythoff sequence of s is s, then s=A003159. (See A184117 for the definition of lower and upper s-Wythoff sequences.)  Starting with any nondecreasing sequence s of positive integers, A003159 is the limit when the lower s-Wythoff operation is iterated.  For example, starting with s=(1,4,9,16,...)=(n^2), we obtain lower and upper s-Wythoff sequences
  a=(1,3,4,5,6,8,9,10,11,12,14,...)=A184427;
  b=(2,7,12,21,31,44,58,74,...)=A184428.
  Then putting s=a and repeating the operation gives a'=(1,3,4,5,7,9,11,12,14,...), which has the same first eight terms as A003159. - Clark Kimberling, Jan 14 2011

			1=1, 3=11, 5=101 and 7=111 have no (0 = even) trailing zeros, 4=100 has 2 (= even) trailing zeros in the base-2 representation.
2=10 and 6=110 end in one (=odd number) of trailing zeros in their base-2 representation, therefore are not terms of this sequence. - _M. F. Hasler_, Oct 29 2013

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Lars Blomberg, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Jean-Paul Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, arXiv preprint arXiv:1401.3727 [math.NT], 2014.
Jean-Paul 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 pp. 3, 6.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
Jean-Paul Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe, and Bruce E. Sagan, A sequence related to that of Thue-Morse, Discrete Math., 139 (1995), 455-461.
Jean-Paul 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.
Jean-Paul Allouche, Jeffrey Shallit, and Guentcho Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math. 292 (2005) 1-15.
George E. Andrews and David Newman, Binary Representations and Theta Functions, 2017.
L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fib. Quart., 10 (1972), 499-518, 550.
R. Clerico, P. Fabbri, and F. Ortenzio, Pericolosamente vicino a Collatz, Rudi Mathematici, N. 226 (Nov 2017), p. 14 (in Italian).
Michael Domaratzki, Trajectory-based codes, Acta Informatica, Volume 40, Numbers 6-7 / May, 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
Artūras Dubickas, On the distance from a rational power to the nearest integer, Journal of Number Theory, Volume 117, Issue 1, March 2006, pp. 222-239.
Artūras Dubickas, On a sequence related to that of Thue-Morse and its applications, Discrete Math. 307 (2007), no. 9-10, 1082--1093. MR2292537 (2008b:11086).
Aviezri S. Fraenkel, New games related to old and new sequences, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (2012), no. 1, 42-46.
Aviezri S. Fraenkel, Home Page.
Russell Jay Hendel, A Family of Sequences Generalizing the Thue Morse and Rudin Shapiro Sequences, arXiv:2505.20547 [cs.FL], 2025. See p. 3.
Clark Kimberling, Problem E2850, Amer. Math. Monthly, 87 (1980), 671.
Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160.
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Slides of talk given at Rutgers University, Feb. 2012.
Jan Snellman, Greedy Regular Convolutions, arXiv:2504.02795 [math.NT], 2025.
Eric Sopena, i-Mark: A new subtraction division game, arXiv:1509.04199 [cs.DM], 2015.
David Wakeham and David R. Wood, On multiplicative Sidon sets, INTEGERS, 13 (2013), #A26.
Index entries for 2-automatic sequences.
Index entries for sequences related to binary expansion of n

For the actual binary numbers see A280049.
Indices of even numbers in A007814.
Complement of A036554, also one-half of A036554.
Cf. A001285, A010060, A000041, A174065, A292118.

import Data.List (delete)
a003159 n = a003159_list !! (n-1)
a003159_list = f [1..] where f (x:xs) = x : f (delete  (2*x) xs)
-- Reinhard Zumkeller, Nov 04 2011

filter:= n -> type(padic:-ordp(n,2),even):
select(filter,[$1..1000]); # Robert Israel, Jul 07 2014

f[n_Integer] := Block[{k = n, c = 0}, While[ EvenQ[k], c++; k /= 2]; c]; Select[ Range[105], EvenQ[ f[ # ]] & ]
Select[Range[150],EvenQ[IntegerExponent[#,2]]&] (* Harvey P. Dale, Oct 19 2011 *)

a(n)=if(n<2,n>0,n=a(n-1); until(valuation(n,2)%2==0,n++); n)

is(n)=valuation(n,2)%2==0 \\ Charles R Greathouse IV, Sep 23 2012

from itertools import count, islice
def A003159_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:(n&-n).bit_length()&1,count(max(startvalue,1)))
A003159_list = list(islice(A003159_gen(),30)) # Chai Wah Wu, Jul 11 2022

def A003159(n):
    def f(x):
        c, s = n+x, bin(x)[2:]
        l = len(s)
        for i in range(l&1^1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Jan 29 2025

a(0) = 1; for n >= 0, a(n+1) = a(n) + 1 if (a(n) + 1)/2 is not already in the sequence, = a(n) + 2 otherwise.
Limit_{n->oo} a(n)/n = 3/2. - Benoit Cloitre, Jun 13 2002
More precisely, a(n) = 3*n/2 + O(log n). - Charles R Greathouse IV, Sep 23 2012
a(n) = Sum_{k = 1..n} A026465(k). - Benoit Cloitre, May 31 2003
a(n+1) = (if a(n) mod 4 = 3 then A007814(a(n) + 1) mod 2 else a(n) mod 2) + a(n) + 1; a(1) = 1. - Reinhard Zumkeller, Aug 03 2003
a(A003157(n)) is even. - Philippe Deléham, Feb 22 2004
Sequence consists of numbers of the form 4^i*(2*j + 1), i>=0, j>=0. - Jon Perry, Jun 06 2004
G.f.: (1/(1-x)) * Product_{k >= 1} (1 + x^A001045(k)). - Paul Barry, Dec 09 2004
a(1) = 1, a(2) = 3, and for n >= 2 we get a(n+1) = 4 + a(n) + a(n-1) - a(a(n)-n+1) - a(a(n-1)-n+2). - Benoit Cloitre, Apr 08 2010
If A(x) is the counting function for a(n) <= x, then A(2^n) = (2^(n+1) + (-1)^n)/3. - Vladimir Shevelev, Apr 15 2010
a(n) = A121539(n) + 1. - Reinhard Zumkeller, Mar 01 2012
A003159 = { N | A007814(N) is even }. - M. F. Hasler, Oct 29 2013

Additional comments from Michael Somos
Edited by M. F. Hasler, Oct 29 2013
Incorrect formula removed by Peter Munn, Dec 04 2020

A035263 Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).

Original entry on oeis.org

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

Offset: 1

Karamanos Konstantinos, N. J. A. Sloane

First Feigenbaum symbolic (or period-doubling) sequence, corresponding to the accumulation point of the 2^{k} cycles through successive bifurcations.
To construct the sequence: start with 1 and concatenate: 1,1, then change the last term (1->0; 0->1) gives: 1,0. Concatenate those 2 terms: 1,0,1,0, change the last term: 1,0,1,1. Concatenate those 4 terms: 1,0,1,1,1,0,1,1 change the last term: 1,0,1,1,1,0,1,0, etc. - Benoit Cloitre, Dec 17 2002
Let T denote the present sequence. Here is another way to construct T. Start with the sequence S = 1,0,1,,1,0,1,,1,0,1,,1,0,1,,... and fill in the successive holes with the successive terms of the sequence T (from paper by Allouche et al.). - Emeric Deutsch, Jan 08 2003 [Note that if we fill in the holes with the terms of S itself, we get A141260. - N. J. A. Sloane, Jan 14 2009]
From N. J. A. Sloane, Feb 27 2009: (Start)
In more detail: define S to be 1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1,0,1___...
If we fill the holes with S we get A141260:
1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0,
........1.........0.........1.........1.........0.......1.........1.........0...
- the result is
1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.0.1.... = A141260.
But instead, if we define T recursively by filling the holes in S with the terms of T itself, we get A035263:
1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0,
........1.........0.........1.........1.........1.......0.........1.........0...
- the result is
1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.1.1.0.1.0.1..0..1.1.1..0..1.0.1.. = A035263. (End)
Characteristic function of A003159, i.e., A035263(n)=1 if n is in A003159 and A035263(n)=0 otherwise (from paper by Allouche et al.). - Emeric Deutsch, Jan 15 2003
This is the sequence of R (=1), L (=0) moves in the Towers of Hanoi puzzle: R, L, R, R, R, L, R, L, R, L, R, R, R, ... - Gary W. Adamson, Sep 21 2003
Manfred Schroeder, p. 279 states, "... the kneading sequences for unimodal maps in the binary notation, 0, 1, 0, 1, 1, 1, 0, 1..., are obtained from the Morse-Thue sequence by taking sums mod 2 of adjacent elements." On p. 278, in the chapter "Self-Similarity in the Logistic Parabola", he writes, "Is there a closer connection between the Morse-Thue sequence and the symbolic dynamics of the superstable orbits? There is indeed. To see this, let us replace R by 1 and C and L by 0." - Gary W. Adamson, Sep 21 2003
Partial sums modulo 2 of the sequence 1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), a(6), ... . - Philippe Deléham, Jan 02 2004
Parity of A007913, A065882 and A065883. - Philippe Deléham, Mar 28 2004
The length of n-th run of 1's in this sequence is A080426(n). - Philippe Deléham, Apr 19 2004
Also parity of A005043, A005773, A026378, A104455, A117641. - Philippe Deléham, Apr 28 2007
Equals parity of the Towers of Hanoi, or ruler sequence (A001511), where the Towers of Hanoi sequence (1, 2, 1, 3, 1, 2, 1, 4, ...) denotes the disc moved, labeled (1, 2, 3, ...) starting from the top; and the parity of (1, 2, 1, 3, ...) denotes the direction of the move, CW or CCW. The frequency of CW moves converges to 2/3. - Gary W. Adamson, May 11 2007
A conjectured identity relating to the partition sequence, A000041: p(x) = A(x) * A(x^2) when A(x) = the Euler transform of A035263 = polcoeff A174065: (1 + x + x^2 + 2x^3 + 3x^4 + 4x^5 + ...). - Gary W. Adamson, Mar 21 2010
a(n) is 1 if the number of trailing zeros in the binary representation of n is even. - Ralf Stephan, Aug 22 2013
From Gary W. Adamson, Mar 25 2015: (Start)
A conjectured identity relating to the partition sequence, A000041 as polcoeff p(x); A003159, and its characteristic function A035263: (1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ...); and A036554 indicating n-th terms with zeros in A035263: (2, 6, 8, 10, 14, 18, 22, ...).
The conjecture states that p(x) = A(x) = A(x^2) when A(x) = polcoeffA174065 = the Euler transform of A035263 = 1/(1-x)*(1-x^3)*(1-x^4)*(1-x^5)*... = (1 + x + x^2 + 2x^3 + 3x^4 + 4x^5 + ...) and the aerated variant = the Euler transform of the complement of A035263: 1/(1-x^2)*(1-x^6)*(1-x^8)*... = (1 + x^2 + x^4 + 2x^6 + 3x^8 + 4x^10 + ...).
(End)
The conjecture above was proved by Jean-Paul Allouche on Dec 21 2013.
Regarded as a column vector, this sequence is the product of A047999 (Sierpinski's gasket) regarded as an infinite lower triangular matrix and A036497 (the Fredholm-Rueppel sequence) where the 1's have alternating signs, 1, -1, 0, 1, 0, 0, 0, -1, .... - Gary W. Adamson, Jun 02 2021
The numbers of 1's through n (A050292) can be determined by starting with the binary (say for 19 = 1 0 0 1 1) and writing: next term is twice current term if 0, otherwise twice plus 1. The result is 1, 2, 4, 9, 19. Take the difference row, = 1, 1, 2, 5, 10; and add the odd-indexed terms from the right: 5, 4, 3, 2, 1 = 10 + 2 + 1 = 13. The algorithm is the basis for determining the disc configurations in the tower of Hanoi game, as shown in the Jul 24 2021 comment of A060572. - Gary W. Adamson, Jul 28 2021

Karamanos, Kostas. "From symbolic dynamics to a digital approach." International Journal of Bifurcation and Chaos 11.06 (2001): 1683-1694. (Full version. See p. 1685)
Karamanos, K. (2000). From symbolic dynamics to a digital approach: chaos and transcendence. In Michel Planat (Ed.), Noise, Oscillators and Algebraic Randomness (Lecture Notes in Physics, pp. 357-371). Springer, Berlin, Heidelberg. (Short version. See p. 359)
Manfred R. Schroeder, "Fractals, Chaos, Power Laws", W. H. Freeman, 1991
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 892, column 2, Note on p. 84, part (a).

Antti Karttunen, Table of n, a(n) for n = 1..65536 (first 10000 terms from T. D. Noe)
Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See p. 6.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
Jean-Paul Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, A sequence related to that of Thue-Morse, Discrete Math., 139 (1995), 455-461.
Jean-Paul Allouche and Michel Mendès 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 Michel 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 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.
Joerg Arndt, Matters Computational (The Fxtbook), pp.9-10, pp.734-738
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
Benoit Cloitre, Fractal walk on the 130000 first terms (step of unit length moving with angle Pi/3 if 0 and -Pi/3 if 1) starting at (0,0)
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
B. Derrida, A. Gervois and Y. Pomeau, Iteration of endomorphisms on the real axis and representation of number, Ann. Inst. Henri Poincaré, Section A: Physique Théorique, Vol. XXIX no. 3, 305-356 (1978).
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 79. Book's website
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Konstantinos Karamanos, Symbolic Dynamics to a Digital Approach, Int. J. of Bifurcation and Chaos, 11(6), 1683-1694 (2001).
Konstantinos Karamanos and Grégoire Nicolis, Symbolic Dynamics and Entropy Analysis of Feigenbaum Limit Sets, Chaos, Solitons and Fractals 10(7), 1135 - 1150 (1999).
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions
Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
Nicholas C. Metropolis, Myron L. Stein and Paul R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44.
Jeffrey Shallit and Anatoly Zavyalov, Transduction of Automatic Sequences and Applications, arXiv:2303.15203 [cs.FL], 2023, see p. 5.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Binary carry sequence.
Eric Weisstein's World of Mathematics, Double-free set.
Index entries for characteristic functions
Index entries for sequences related to binary expansion of n
Index entries for sequences that are fixed points of mappings

Parity of A001511. Anti-parity of A007814.
Absolute values of first differences of A010060. Apart from signs, same as A029883. Essentially the same as A056832.
Swapping 0 and 1 gives A096268.
Cf. A033485, A050292 (partial sums), A089608, A088172, A019300, A039982, A073675, A121701, A141260, A000041, A174065, A220466, A154269 (Mobius transform).
Limit of A317957(n) for large n.
Cf. A060572

import Data.Bits (xor)
a035263 n = a035263_list !! (n-1)
a035263_list = zipWith xor a010060_list $ tail a010060_list
-- Reinhard Zumkeller, Mar 01 2012

nmax:=105: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := (p+1) mod 2 od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Feb 07 2013
A035263 := n -> 1 - padic[ordp](n, 2) mod 2:
seq(A035263(n), n=1..105); # Peter Luschny, Oct 02 2018

a[n_] := a[n] = If[ EvenQ[n], 1 - a[n/2], 1]; Table[ a[n], {n, 1, 105}] (* Or *)
Rest[ CoefficientList[ Series[ Sum[ x^(2^k)/(1 + (-1)^k*x^(2^k)), {k, 0, 20}], {x, 0, 105}], x]]
f[1] := True; f[x_] := Xor[f[x - 1], f[Floor[x/2]]]; a[x_] := Boole[f[x]] (* Ben Branman, Oct 04 2010 *)
a[n_] := If[n == 0, 0, 1 - Mod[ IntegerExponent[n, 2], 2]]; (* Jean-François Alcover, Jul 19 2013, after Michael Somos *)
Nest[ Flatten[# /. {0 -> {1, 1}, 1 -> {1, 0}}] &, {0}, 7] (* Robert G. Wilson v, Jul 23 2014 *)
SubstitutionSystem[{0->{1,1},1->{1,0}},1,{7}][[1]] (* Harvey P. Dale, Jun 06 2022 *)

{a(n) = if( n==0, 0, 1 - valuation(n, 2)%2)}; /* Michael Somos, Sep 04 2006 */

{a(n) = if( n==0, 0, n = abs(n); subst( Pol(binary(n)) - Pol(binary(n-1)), x, 1)%2)}; /* Michael Somos, Sep 04 2006 */

{a(n) = if( n==0, 0, n = abs(n); direuler(p=2, n, 1 / (1 - X^((p<3) + 1)))[n])}; /* Michael Somos, Sep 04 2006 */

def A035263(n): return (n&-n).bit_length()&1 # Chai Wah Wu, Jan 09 2023

(define (A035263 n) (let loop ((n n) (i 1)) (cond ((odd? n) (modulo i 2)) (else (loop (/ n 2) (+ 1 i)))))) ;; (Use mod instead of modulo in R6RS) Antti Karttunen, Sep 11 2017

Absolute values of first differences (A029883) of Thue-Morse sequence (A001285 or A010060). Self-similar under 10->1 and 11->0.
Series expansion: (1/x) * Sum_{i>=0} (-1)^(i+1)*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*(floor((n+1)/2^k)-floor(n/2^k)). - Benoit Cloitre, Jun 03 2003
Another g.f.: Sum_{k>=0} x^(2^k)/(1+(-1)^k*x^(2^k)). - Ralf Stephan, Jun 13 2003
a(2*n) = 1-a(n), a(2*n+1) = 1. - Ralf Stephan, Jun 13 2003
a(n) = parity of A033485(n). - Philippe Deléham, Aug 13 2003
Equals A088172 mod 2, where A088172 = 1, 2, 3, 7, 13, 26, 53, 106, 211, 422, 845, ... (first differences of A019300). - Gary W. Adamson, Sep 21 2003
a(n) = a(n-1) - (-1)^n*a(floor(n/2)). - Benoit Cloitre, Dec 02 2003
a(1) = 1 and a(n) = abs(a(n-1) - a(floor(n/2))). - Benoit Cloitre, Dec 02 2003
a(n) = 1 - A096268(n+1); A050292 gives partial sums. - Reinhard Zumkeller, Aug 16 2006
Multiplicative with a(2^k) = 1 - (k mod 2), a(p^k) = 1, p > 2. Dirichlet g.f.: Product_{n = 4 or an odd prime} (1/(1-1/n^s)). - Christian G. Bower, May 18 2005
a(-n) = a(n). a(0)=0. - Michael Somos, Sep 04 2006
Dirichlet g.f.: zeta(s)*2^s/(2^s+1). - Ralf Stephan, Jun 17 2007
a(n+1) = a(n) XOR a(ceiling(n/2)), a(1) = 1. - Reinhard Zumkeller, Jun 11 2009
Let D(x) be the generating function, then D(x) + D(x^2) == x/(1-x). - Joerg Arndt, May 11 2010
a(n) = A010060(n) XOR A010060(n+1); a(A079523(n)) = 0; a(A121539(n)) = 1. - Reinhard Zumkeller, Mar 01 2012
a((2*n-1)*2^p) = (p+1) mod 2, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 07 2013
a(n) = A000035(A001511(n)). - Omar E. Pol, Oct 29 2013
a(n) = 2-A056832(n) = (5-A089608(n))/4. - Antti Karttunen, Sep 11 2017, after Benoit Cloitre
For n >= 0, a(n+1) = M(2n) mod 2 where M(n) is the Motzkin number A001006 (see Deutsch and Sagan 2006 link). - David Callan, Oct 02 2018
a(n) = A038712(n) mod 3. - Kevin Ryde, Jul 11 2019
Given any n in the form (k * 2^m, k odd), extract k and m. Categorize the results into two outcomes of (k, m, even or odd). If (k, m) is (odd, even) substitute 1. If (odd, odd), denote the result 0.  Example: 5 = (5 * 2^0), (odd, even, = 1). (6 = 3 * 2^1), (odd, odd, = 0). - Gary W. Adamson, Jun 23 2021

Alternative description added to the name by Antti Karttunen, Sep 11 2017

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Characteristic function of A001969 (evil numbers). - Ralf Stephan, Jun 20 2003
From Gary W. Adamson, Aug 24 2008: (Start)
Parity of A143579 (Odious numbers (A000069) interleaved with Evil numbers (A001969)).
Two conjectures: If n is even, the ratio of 1's to 0's = 1:1.
There are no three adjacent terms of the same parity. (End)
Conjecture (verified for the first 280000 entries): this is the characteristic function of A001969. - R. J. Mathar, Sep 05 2008
From Michel Dekking, Jan 05 2021: (Start)
Proof of these three conjectures: the first two follow directly from the third, because the sequence A010059 is the binary complement of the Thue-Morse sequence A010060.
For the third conjecture: the odious and evil numbers occur as quadruples EOOE and OEEO, simply by their definition. To obtain the mod 2 version of the interleave of the odious and evil numbers we therefore have to apply a transformation
      EOOE -> OEOE, OEEO -> OEOE to these quadruples.
But this changes the parities from the corresponding 4n, 4n+1, 4n+2, 4n+3 quadruples from 0101 to 1001 in the first case, and from 0101 to 0110 in the second case. Since the quadruples EOOE and OEEO occur in a Thue Morse pattern, then also the quadruples 1001 and 0110 occur in a Thue Morse pattern, finishing the proof.
(End)

			The evolution starting at 1 is:
.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
...........

W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.
A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.

Robert Israel, Table of n, a(n) for n = 0..10000
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.
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
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, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
Michael Gilleland, Some Self-Similar Integer Sequences
G. A. Hedlund, Remarks on the work of Axel Thue on sequences, Nordisk Mat. Tid., 15 (1967), 148-150.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
H. M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22 (1921), 84-100.
Stephen Wolfram, A New Kind Of Science | Online.
Index entries for sequences related to binary expansion of n
Index entries for characteristic functions

Cf. A001285 (1, 2 version), A010060 (0, 1 version), A106400 (+1, -1 version), A059448 (with reversed subsections).
Cf. also A000069, A026147, A159481.
Cf. A000120, A001969, A143579.

a010059 = (1 -) . a010060  -- Reinhard Zumkeller, Feb 04 2013

A010059 := n->1-A010060(n);
map(t->49-t,convert(StringTools[ThueMorse](1000),bytes)); # Robert Israel, Feb 02 2016
# second Maple program:
a := n -> ifelse(type(add(convert(n, base, 2)), even), 1, 0):
seq(a(n), n = 0 .. 104); # Peter Luschny, Mar 11 2024

Mod[ CoefficientList[Series[(1 + Sqrt[(1 - 3x)/(1 + x)])/(2(1 + x)), {x, 0, 111}], x], 2] (* Stephan Wolfram *)
CoefficientList[ Series[1/(1 - x) + Product[1 - x^2^k, {k, 0, 10}], {x, 0, 111}]/2, x] (* Robert G. Wilson v, Jul 16 2004 *)
Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {1}, 7] (* Robert G. Wilson v Sep 26 2006 *)
od = Select[ Range[0, 129], OddQ@ DigitCount[ #, 2, 1] &]; ev = Select[ Range[0, 129], EvenQ@ DigitCount[ #, 2, 1] &]; Mod[ Flatten@ Transpose[{od, ev}], 2] (* Robert G. Wilson v, Apr 14 2009 *)
Nest[ Join[ #, Mod[2# + 1, 3]] &, {1}, 7] (* Robert G. Wilson v, Jul 27 2014 *)
{{1}}~Join~SubstitutionSystem[{0 -> {0, 1}, 1 -> {1, 0}}, {0}, 6] // Flatten (* Michael De Vlieger, Aug 15 2016, Version 10.2 *)
1 - ThueMorse[Range[0, 100]] (* Paolo Xausa, Oct 25 2024 *)

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

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

maxrow <- 8 # by choice
b01 <- 0
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(1,b01))
# Yosu Yurramendi, Apr 10 2017

G.f.: (1/2) * (1/(1-x) + Product_{k>=0} (1 - x^2^k)). - Ralf Stephan, Jun 20 2003
a(n) = A143579(n) mod 2. - Gary W. Adamson, Aug 24 2008
a(n) + A010060(n) = 1 for all n.
a(n) = A159481(n+1) - A159481(n). - Reinhard Zumkeller, Apr 16 2009
a(n) + A026147(n-1) = 2n for n >= 1. - Clark Kimberling, Oct 06 2014
a(n) = A000069(n+1) (mod 2). - John M. Campbell, Jun 30 2016
a(n) = A059448(A054429(n)) = (A106400(n)+1)/2 = (1+A008836(A005940(1+n)))/2. - Antti Karttunen, May 30 2017
If A(n)=(a(0),a(2),...,a(2^n-1)), then A(n+1)=(A(n),1-A(n)). - Arie Bos, Jul 27 2022
a(n) = (1 + (-1)^A000120(n))/2. - Lorenzo Sauras Altuzarra, Mar 10 2024

cp's OEIS Frontend

A324479 Decimal expansion of real number whose continued fraction expansion is [0, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, ...] (the Thue-Morse sequence A001285).

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Mathematica

Extensions

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

A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Formula

Extensions

A001316 Gould's sequence: a(n) = Sum_{k=0..n} (binomial(n,k) mod 2); number of odd entries in row n of Pascal's triangle (A007318); a(n) = 2^A000120(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Scheme

Formula

Extensions

A003159 Numbers whose binary representation ends in an even number of zeros.

Views

Author

Keywords

Comments