cp's OEIS Frontend

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

It appears that the sequence can be calculated by any of the following methods:

(1) Start with 1 and repeatedly replace 1 with 1, 2, 1 and 2 with 1, 2, 2, 2, 1;

(2) a(1) = 1, all terms are either 1 or 2 and, for n > 0, a(n) = 1 if the length of the n-th run of 2's is 1; a(n) = 2 if the length of the n-th run of consecutive 2's is 3, with each run of 2's separated by a run of two 1's;

(3) replace each 3 in A080426 with 2. - John W. Layman, Feb 18 2003

Number of representations of n as a sum of Jacobsthal numbers (1 is allowed twice as a part). Partial sums are A003159. With interpolated zeros, g.f. is (Product_{k>=1} (1 + x^A078008(k)))/2. - Paul Barry, Dec 09 2004

In other words, the consecutive 0's or 1's in A010060 or A010059. - Robin D. Saunders (saunders_robin_d(AT)hotmail.com), Sep 06 2006

From Carlo Carminati, Feb 25 2011: (Start)

The sequence (starting with the second term) can also be calculated by the following method:

Apply repeatedly to the string S_0 = [2] the following algorithm: take a string S, double it, if the last figure is 1, just add the last figure to the previous one, if the last figure is greater than one, decrease it by one unit and concatenate a figure 1 at the end. (This algorithm is connected with the interpretation of the sequence as a continued fraction expansion.) (End)

This sequence, starting with the second term, happens to be the continued fraction expansion of the biggest cluster point of the set {x in [0,1]: F^k(x) >= x, for all k in N}, where F denotes the Farey map (see A187061). - Carlo Carminati, Feb 28 2011

Starting with the second term, the fixed point of the substitution 2 -> 211, 1 -> 2. - Carlo Carminati, Mar 03 2011

It appears that this sequence contains infinitely many distinct palindromic subsequences. - Alexander R. Povolotsky, Oct 30 2016

From Michel Dekking, Feb 13 2019: (Start)

Let tau defined by tau(0) = 01, tau(1) = 10 be the Thue-Morse morphism, with fixed point A010060. Consecutive runs in A010060 are 0, 11, 0, 1, 00, 1, 1, ..., which are coded by their lengths 1, 2, 1, 1, 2, ... Under tau^2 consecutive runs are mapped to consecutive runs:

tau^2(0) = 0110, tau^2(1) = 1001,

tau^2(00) = 01100110, tau^2(11) = 10011001.

The reason is that (by definition of a run!) runs of 0's and runs of 1's alternate in the sequence of runs, and this is inherited by the image of these runs under tau^2.

Under tau^2 the runs of length 1 are mapped to the sequence 1,2,1 of run lengths, and the runs of length 2 are mapped to the sequence 1,2,2,2,1 of run lengths. This proves John Layman's conjecture number (1): it follows that (a(n)) is fixed point of the morphism alpha

alpha: 1 -> 121, 2 -> 12221.

Since alpha(1) and alpha(2) are both palindromes, this also proves Alexander Povolotsky's conjecture.

(End)

Number of 1's between successive 0's in A010060.

The infinite sequence is abcacbabcbac... which is encoded with a->2, b->1, c->0 to produce this integer sequence.

From Jeffrey Shallit, Dec 07 2019: (Start)

This word is sometimes called 'vtm'; see, for example, see the Blanchet-Sadri et al. reference.

It is a squarefree word containing no instances of the factor 010 or 212 (or cbc, aba in the encoding).

Berstel proved many different definitions (e.g., Braunholtz, Istrail) of the word are equivalent. (End)

Also lengths of successive runs of 1's in the Thue-Morse sequence A010059.

Also lengths of successive runs of 1's in the Thue-Morse sequence A001285.