A005942 -id:A005942 - cp's OEIS frontend

A214213 Erroneous version of A005942.

1, 2, 4, 6, 2, 12, 16, 4, 6, 24, 28, 32, 36, 8, 10, 12, 14, 48, 52, 56, 60, 64, 68, 72, 76, 16, 18, 20, 22, 24, 26, 28, 30, 96, 100, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 192, 196, 200, 204, 208, 212, 216, 220, 224, 228, 232, 236, 240, 244, 248, 252, 256, 260, 264

Offset: 0

N. J. A. Sloane, Jul 10 2012

dead

F. Mignosi, A. Restivo, M. Sciortino, Words and forbidden factors, WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096). Example 20, page 11, the complexity g_t(n) of the Thue-Morse word A010060. There is a typo in the fourth clause of the definition of g_t(n).
Included in accordance with the OEIS policy of including incorrect published sequences with pointers to the correct versions.

Cf. A005942.

f:=proc(n) local m;
if n <= 2 then 2^n;
else m:=floor(log(n-1)/log(2))-1;
     if n <= 3*2^m then 4*n-2^(m+1)-4;
     else 2*n-2^(m+2)-2; # should have been 2*n+2^(m+2)-2
     fi;
fi;
end;

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.

Original entry on oeis.org

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)

A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43

Offset: 1

N. J. A. Sloane

a(n+1) is the second-order survivor of the n-person Josephus problem where every second person is marked until only one remains, who is then eliminated; the process is repeated from the beginning until all but one is eliminated. a(n) is first a power of 2 when n is three times a power of 2. For example, the first appearances of 2, 4, 8 and 16 are at positions 3, 6, 12 and 24, or (3*1),(3*2),(3*4) and (3*8). Eugene McDonnell (eemcd(AT)aol.com), Jan 19 2002, reporting on work of Boyko Bantchev (Bulgaria).
Appears to coincide with following sequence: Let n >= 1. Start with a bag B containing n 1's. At each step, replace the two least elements x and y in B with the single element x+y. Repeat until B contains 2 or fewer elements. Let a(n) be the largest element remaining in B at this point. - David W. Wilson, Jul 01 2003
Hsien-Kuei Hwang, S Janson, TH Tsai (2016) show that A078881 is the same sequence, apart from the offset. - N. J. A. Sloane, Nov 26 2017

			From _Peter Bala_, Aug 01 2022: (Start)
1) The sequence {n - a(a(n)) : n >= 1} begins [0, 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 9, 10, 11, 12, 12, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, ...] has the repeated values 3 (twice), 6 (three times), 12 (five times), 24 (nine times), 48 (seventeen times) ..., conjecturally of the form 3*2^m
2) The sequence {n - a(a(a(n))) : n >= 1} begins [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 14, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 28, 28, 28, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, ...] has the repeated values 7 (twice), 14 (three times), 28 (five times), 56 (nine times) ..., conjecturally of the form 7*2^m. (End)

J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 85-94.
Hsien-Kuei Hwang, S Janson, TH 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; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also 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
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..1024
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Dale Gerdemann, Second-Order Josephus Problem (video)
Jeffrey Shallit, Intertwining of Complementary Thue-Morse Factors, arXiv:2203.02917 [cs.FL], 2022.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to the Josephus Problem

Cf. A053644, A060973, A066997, A078881.

a := proc (n) option remember; if n = 1 then 1 else n - a(n - a(a(n-1))) end if end proc: seq(a(n), n = 1..100); # Peter Bala, Jul 31 2022

t = {1, 1}; Do[If[OddQ[n], AppendTo[t, t[[Floor[n/2]]] + t[[Ceiling[n/2]]]], AppendTo[t, 2*t[[n/2]]]], {n, 3, 128}] (* T. D. Noe, May 25 2011 *)

a(n) = my(i=logint(n,2)-1); if(bittest(n,i), 2<Kevin Ryde, Aug 06 2022

a(n)=if(n<2,1,n-a(n-a(n\2))); \\ Benoit Cloitre, May 12 2024

from functools import lru_cache
@lru_cache(maxsize=None)
def A006165(n): return 1 if n <= 2 else A006165(n//2) + A006165((n+1)//2) # Chai Wah Wu, Mar 08 2022

def A006165(n): return min(n-(m:=1<1 else 1 # Chai Wah Wu, Oct 22 2024

For n >= 2, if a(n) >= A006257(n), i.e., if msb(n) > n - a(n)/2, then a(n+1) = a(n)+1, otherwise a(n+1) = a(n). - Henry Bottomley, Jan 21 2002
a(n+1) = min(msb(n), 1+n-msb(n)/2) for all n (msb = most significant bit, A053644). - Boyko Bantchev (bantchev(AT)math.bas.bg), May 17 2002
a(1)=1, a(n) = n - a(n - a(a(n-1))). - Benoit Cloitre, Nov 08 2002
a(1)=1, a(n) = n - a(n - a(floor(n/2))). - Benoit Cloitre, May 12 2024
For k > 0, 0 <= i <= 2^k-1, a(2^k+i) = 2^(k-1)+i; for 2^k-2^(k-2) <= x <= 2^k a(x) = 2^(k-1); (also a(m*2^k) = a(m)*2^k for m >= 2). - Benoit Cloitre, Dec 16 2002
G.f.: x * (1/(1+x) + (1/(1-x)^2) * Sum_{k>=0} t^2*(1-t)) where t = x^2^k. - Ralf Stephan, Sep 12 2003
a(n) = A005942(n+1)/2 - n = n - A060973(n) = 2n - A007378(n). - Ralf Stephan, Sep 13 2003
a(n) = A080776(n-1) + A060937(n). - Ralf Stephan
From Peter Bala, Jul 31 2022: (Start)
For k a positive integer, define the k-th iterated sequence a^(k) of a by a^(1)(n) = a(n) and setting a^(k)(n) = a^(k-1)(a(n)) for k >= 2. For example, a^(2)(n) = a(a(n)) and a^(3)(n) = a(a(a(n))).
Conjectures: for n >= 2 there holds
(i) a(n) + a(n - a(n - a(n - a(n - a(n))))) = n;
(ii) a(n - a(n - a(n - a(n)))) = a(n - a(n - a(n - a(n - a(n - a(n))))));
(iii) a^2(n) = a(n - a(n - a(n - a(n))));
(iv) n - a(n) = a(n - a^(2)(n));
(v) a(n - a(n)) = a^(2)(n - a^(2)(n - a^(2)(n - a^(2)(n))));
(vi) for k >= 2, a^(k)(n - a^(k)(n)) = a^(k)(n - a^(k)(n - a^(k)(n - a^(k)(n)))).
(vii) for k >= 1, the sequence {n - a^(k)(n) : n >= 1} has first differences either 0 or 1. We conjecture that the repeated values of the sequence are of the form (2^k - 1)*2^m. The number of repeated values appears to always be 2, 3, 5, 9, 17, 35, ..., independent of k, conjecturally A000051. Two examples are given below.
A similar property may hold for the sequences {n - A060973^(k)(n) : n >= 2^(k-1)}, k = 1,2,3,.... (End)

More terms from Larry Reeves (larryr(AT)acm.org), Jun 12 2002

A006697 Number of subwords of length n in infinite word generated by a -> aab, b -> b.

Original entry on oeis.org

1, 2, 4, 6, 9, 13, 17, 22, 28, 35, 43, 51, 60, 70, 81, 93, 106, 120, 135, 151, 167, 184, 202, 221, 241, 262, 284, 307, 331, 356, 382, 409, 437, 466, 496, 527, 559, 591, 624, 658, 693, 729, 766, 804, 843, 883, 924, 966, 1009, 1053, 1098, 1144, 1191, 1239

Offset: 0

N. J. A. Sloane and Jeffrey Shallit

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

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, On the subword complexity of the fixed point of a -> aab, b -> b, and generalizations, arXiv preprint arXiv:1605.02361 [math.CO], 2016.
Gabriele Fici, The Shortest Interesting Binary Words, arXiv:2412.21145 [math.CO], 2024. See p. 12.

Cf. A005943, A005942, A094913, A134457, A134466.

A103354[n_] := Floor[ FullSimplify[ ProductLog[ 2^n*Log[2]]/Log[2]]]; Accumulate[ Table[ A103354[n], {n, 1, 54}]] (* Jean-François Alcover, Dec 13 2011, after M. F. Hasler *)

LambertW(y) = solve( X=1,log(y), X*exp(X)-y)
A006697(n,b=2)=local(m=floor(n+1-LambertW(b^(n+1)*log(b))/log(b)));(b^(m+1)-1)/(b-1)+(n-m)*(n-m+1)/2 \\ M. F. Hasler, Dec 14 2007

G.f.: 1 + 1/(1-x) + 1/(1-x)^2 * [1/(1-x) - sum(k>=1, x^(2^k+k-1))] (conjectured). - Ralf Stephan, Mar 05 2004
Conjectures: partial sums of A103354, also equal to A094913(n) + 1. - Vladeta Jovovic, Sep 19 2005
a(n) = sum(k=0,n,min(2^k,n-k+1)) = 2^(m+1)-1 + (n-m)(n-m+1)/2 with m = [ n+1-LambertW( 2^(n+1) * log(2) ) / log(2) ] = integer part of the solution to 2^m = n+1-m. (conjectured). - M. F. Hasler, Dec 14 2007

More terms from Michel ten Voorde, Apr 11 2001

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

Original entry on oeis.org

1, 2, 4, 8, 16, 24, 36, 46, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128, 136, 144, 152, 160, 168, 176, 184, 192, 200, 208, 216, 224, 232, 240, 248, 256, 264, 272, 280, 288, 296, 304, 312, 320, 328, 336, 344, 352, 360, 368, 376, 384, 392, 400, 408, 416, 424, 432, 440, 448, 456, 464, 472, 480, 488, 496, 504

Offset: 0

N. J. A. Sloane, Jeffrey Shallit

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

			All 8 subwords of length three (000, 001, ..., 111) occur in A020987, so a(3) = 8.

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

David A. Corneth, Table of n, a(n) for n = 0..9999
Jean-Paul Allouche, The Number of Factors in a Paperfolding Sequence, Bulletin of the Australian Mathematical Society, volume 46, number 1, August 1992, pages 23-32. Section 6 theorem 2, a(n) = P_{w_i}(n).
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A006697, A005942, A337120 (paperfolding).

# Naive Maple program, useful for getting initial terms of factor complexity FC of a sequence b1[]. N. J. A. Sloane, Jun 04 2019
FC:=[0]; # a(0)=0 from the empty subword
for L from 1 to 12 do
  lis := {};
  for n from 1 to nops(b1)-L do
    s:=[seq(b1[i],i=n..n+L-1)];
    lis:={op(lis),s}; od:
FC:=[op(FC),nops(lis)];
od:
FC;

CoefficientList[Series[(1 + x^2 + 2 x^3 + 4 x^4 + 4 x^6 - 2 x^7 - 2 x^9)/(1 - x)^2, {x, 0, 64}], x] (* Michael De Vlieger, Oct 14 2021 *)

first(n) = n = max(n, 10); concat([1, 2, 4, 8, 16, 24, 36, 46], vector(n-8,i,8*i+48)) \\ David A. Corneth, Apr 28 2021

G.f.: (1+x^2+2*x^3+4*x^4+4*x^6-2*x^7-2*x^9)/(1-x)^2. - Joerg Arndt, Jun 10 2012
From Kevin Ryde, Aug 18 2020: (Start)
a(1..7) = 2,4,8,16,24,36,46, then a(n) = 8*n - 8 for n>=8. [Allouche]
a(n) = 2*A337120(n-1) for n>=1. [Allouche, end of proof of theorem 2]
(End)

Minor edits by N. J. A. Sloane, Jun 06 2012
a(14)-a(32) added by Joerg Arndt, Jun 10 2012
a(33)-a(36) added by Joerg Arndt, Oct 28 2012

A275202 Subword complexity (number of distinct blocks of length n) of the period doubling sequence A096268.

Original entry on oeis.org

2, 3, 5, 6, 8, 10, 11, 12, 14, 16, 18, 20, 21, 22, 23, 24, 26, 28, 30, 32, 34, 36, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 161, 162, 163, 164, 165

Offset: 1

Daniel Rust, Jul 19 2016

			For n = 1 there are two words {0,1}.
For n = 2 there are three words {00,01,10}.
For n = 3 there are five words {000,001,010,100,101}.

Jinyuan Wang, Table of n, a(n) for n = 1..1000
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
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.

Cf. A006165, A096268, A035263, A005942.

a := proc(n) option remember; if n = 1 then 2 elif n = 2 then 3 else a(iquo(n,2)) + a(iquo(n+1,2)) end if; end proc:
seq(a(n), n = 1..100); # Peter Bala, Aug 05 2022

t = Nest[Flatten[# /. {0 -> {1, 0}, 1 -> {0, 0}}] &, {1}, 12]; Table[2^n - Count[SequencePosition[t, #] & /@ Tuples[{0, 1}, n], {}], {n, 16}] (* Michael De Vlieger, Jul 19 2016, Version 10.1, after Robert G. Wilson v at A096268 *)

lista(nn) = {my(v=vector(nn-nn%2)); v[1]=2; v[2]=3; for(n=2, nn\2, v[2*n-1]=v[n-1]+v[n]; v[2*n]=2*v[n]); v; } \\ Jinyuan Wang, Feb 27 2020

a(n) = my(k=logint(n,2)-1); if(bittest(n,k), n + 2<Kevin Ryde, Aug 09 2022

a(n) = A005942(n+1)/2, and the latter satisfies a simple recurrence. - N. J. A. Sloane, Jun 04 2019

Proof: let b(n) = A096268(n) and c(n) = b(2n+1). For n >= 2, distinct blocks of length 2n are of the form 0_0_...0_ or 0_0..._0, and distinct blocks of length 2n-1 are of the form 0_0...0 or _0_0...0. Therefore, a(2n) is twice the n-subword complexity of {c(k)}, and a(2n-1) is the sum of (n-1)-subword complexity and n-subword complexity of {c(k)}. Note that n-subword complexity of {c(k)} is a(n) because c(2k) = b(4k+1) = 1, c(4k+1) = b(8k+3) = b(2k) = 0 and c(4k+3) = b(8k+7) = b(2k+1) = c(k). In conclusion, a(2n) = 2a(n) and a(2n-1) = a(n-1) + a(n), with a(1) = 2 and a(2) = 3. So a(n) = A005942(n+1)/2. - Jinyuan Wang, Feb 27 2020

A086694 A run of 2^n 1's followed by a run of 2^n 0's, for n=0, 1, 2, ...

Original entry on oeis.org

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

Offset: 1

Ralf Stephan, Sep 12 2003

First differences of A006165 and, likely, of A078881.

Robert Israel, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A005942, A079944.

seq(op([1$(2^n),0$(2^n)]),n=0..6); # Robert Israel, Jul 27 2017

Table[{PadRight[{},2^n,1],PadRight[{},2^n,0]},{n,0,5}]//Flatten (* Harvey P. Dale, May 29 2017 *)
Table[{Array[1&,2^n],Array[0&,2^n]},{n,0,5}]//Flatten (* Wolfgang Hintze, Jul 27 2017 *)

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

a(n) = 1-A079944(n-1) = 2-A079882(n-1) = A080791(n+1)-A083661(n+1).
a(n) = 1 - floor(log_2(4*(n+1)/3)) + floor(log_2(n+1)).
a(1) = 1, a(2) = 0, a(2n+1) = a(n), a(2n) = a(n-1).
G.f.: Sum_{k>=1} (x^(2^k)-x^(3*2^(k-1)))/(x-x^2). - Robert Israel, Jul 27 2017
G.f.: g(x) = (1/(1 - x))*( Sum_{n >= 1} x^(2^n-1)*(1 - x^2^(n-1)) ). Functional equation: g(x) = x + x*(1+x)*g(x^2). - Wolfgang Hintze, Aug 05 2017

A214212 Number of right special factors of length n in the Thue-Morse sequence A010060.

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 4, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 0

N. J. A. Sloane, Jul 10 2012

nonn

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

Robert Israel, Table of n, a(n) for n = 0..10000
S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96.
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.

Cf. A010060, A005942, A212214.

ph:=proc(n) option remember;
if n=2 then 2 elif n<=3 then n+1 else if n mod 2 = 0 then ph(n/2) else ph((n+1)/2); fi;
fi; end;

ph[n_] := ph[n] = If[n == 2, 2, If[n <= 3, n+1, If[Mod[n, 2] == 0, ph[n/2], ph[(n+1)/2]]]];
ph /@ Range[0, 120] (* Jean-François Alcover, Jun 18 2020, after Maple *)

A005942(n+1) - A005942(n). - Michel Dekking, Sep 28 2020

Name clarified by Michel Dekking, Sep 28 2020

A214215 List of subwords (or factors) of the Thue-Morse "1,2"-word A001285.

Original entry on oeis.org

1, 2, 11, 12, 21, 22, 112, 121, 122, 211, 212, 221, 1121, 1122, 1211, 1212, 1221, 2112, 2121, 2122, 2211, 2212, 11212, 11221, 12112, 12122, 12211, 12212, 21121, 21122, 21211, 21221, 22112, 22121, 112122, 112211, 112212, 121121, 121122, 121221, 122112, 122121

Offset: 1

N. J. A. Sloane, Jul 10 2012

nonn

The number of factors of length m is given by A005942(m).

Alois P. Heinz, Table of n, a(n) for n = 1..10200

Cf. A001285, A010060, A005942.

b:= proc(n) option remember; local r;
      `if`(n=0, 1, `if`(n<4, 2*n, `if`(irem(n, 2, 'r')=0,
       b(r)+b(r+1), 2*b(r+1))))
    end:
m:= proc(n) option remember; local r;
      `if`(n=0, 1, `if`(irem(n, 2, 'r')=0, m(r), 3-m(r)))
    end:
T:= proc(n) local k, s; s:={};
      for k while nops(s)Alois P. Heinz, Jul 19 2012

b[n_] := b[n] = Module[{r}, If[n == 0, 1, If[n < 4, 2n, r = Quotient[n, 2]; If[Mod[n, 2] == 0, b[r] + b[r + 1], 2b[r + 1]]]]];
m[n_] := m[n] = Module[{r}, If[n == 0, 1, r = Quotient[n, 2]; If[Mod[n, 2] == 0, m[r], 3 - m[r]]]];
T[n_] := Module[{k, s = {}}, For[k = 1,  Length[s] < b[n], k++, s = s  ~Union~ {FromDigits[#]}& @ Table[m[i], {i, k, k + n - 1}]]; Sort[s]];
Array[T, 10] // Flatten (* Jean-François Alcover, Nov 22 2020, after Alois P. Heinz *)

A365624 a(n) is the length of the longest word w in the Thue-Morse sequence (A010060) in which every length-n factor of w is unique.

Original entry on oeis.org

2, 5, 8, 12, 16, 18, 24, 26, 32, 34, 36, 38, 48, 50, 52, 54, 64, 66, 68, 70, 72, 74, 76, 78, 96, 98, 100, 102, 104, 106, 108, 110, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 192, 194, 196, 198, 200, 202, 204, 206

Offset: 1

Gandhar Joshi, Sep 13 2023

nonn

Interestingly, 5 is the only odd number in the list so far.

			The length of the longest word in Thue-Morse sequence that admits only unique length-2 factors is 5. For example, 11001 (which is not the only one). Hence a(2)=5.

Kevin Ryde, Table of n, a(n) for n = 1..8192
Kevin Ryde, PARI/GP Code

Cf. A010060, A005942 (subword complexity), A366408 (first location).

PARI
```
\\ See links.
```

def tmfaceq "At (t T[i+t]=T[j+t]"; % Check if two length-n factors of Thue-Morse at positions i and j are equal; T is predefined in Walnut as the DFA that recognises Thue-Morse sequence. %
def tm_w_len_N_unique_factors "Ei (Aj,k (i<=j & j<(i+n-N) & j ~$tmfaceq(j,k,N))": % Find lengths of words with length-N unique factors; must replace N with a constant %
def longest_len_N "$tm_w_len_N_unique_factors(n) & Am (m>n) => ~$tm_w_len_N_unique_factors(m)"; % Check the longest of the lengths found in previous line; must replace N with the same constant %

cp's OEIS Frontend

A214213 Erroneous version of A005942.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A006697 Number of subwords of length n in infinite word generated by a -> aab, b -> b.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A275202 Subword complexity (number of distinct blocks of length n) of the period doubling sequence A096268.

Views

Author

Keywords

Examples