# [seqfan] Re: A connection between the Thue-Morse sequence A010060 and A000123

jean-paul allouche jean-paul.allouche at imj-prg.fr
Fri Nov 11 10:43:57 CET 2016

Dear Vladimir

If you look at the generating function of the Thue-Morse sequence
with values $\pm 1$ (see http://oeis.org/A106400), it is essentially
the inverse of the generating function of A000123. This is known, see,
e.g., Page 191 in the paper by J. Shallit and myself, The ring of k-regular
sequences, Theoret. Comput. Sci. (98) 1992 163--197, freely available at
http://www.sciencedirect.com/science/article/pii/030439759290001V

best wishes
jean-paul

Le 11/11/16 à 00:12, Vladimir Reshetnikov a écrit :
> Dear SeqFans,
>
> The Thue-Morse sequence [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, ...]
> appears in the OEIS as http://oeis.org/A010060. It can be constructed
> starting with 0 and repeatedly appending the binary complement of already
> constructed part. Also, A010060(n) can be thought of as the parity of the
> number of 1s in the binary representation of n.
>
> Consider a power series f(x) = Sum_{n>=0} (-1)^A010060(n) * x^n = 1 - x -
> x^2 + x^3 - x^4 + x^5 + x^6 - x^7 - x^8 + ...
>
> Here is a graph of the function represented by this power series (if you
> cannot see the graph inline in this message, you should be able to find it
> at http://s16.postimg.org/c2qiykfud/Thue_Morse.png).
>
>
> ​
> Its reciprocal (multiplicative inverse) is 1/f(x) = 1 + x + 2*x^2 + 2*x^3 +
> 4*x^4 + 4*x^5 + 6*x^6 + 6*x^7 + 10*x^8 + 10*x^9 + ..., where the
> coefficients seem to go in pairs: [1, 1, 2, 2, 4, 4, 6, 6, 10, 10, ...].
> Taking a bisection, we get the sequence [1, 2, 4, 6, 10, 14, 20, 26, 36,
> 46, 60, 74, 94, 114, 140, 166, ...]. A lookup in the OEIS returns a
> possible match http://oeis.org/A000123, whose name is "Number of binary
> partitions: number of partitions of 2n into powers of 2", and which has a
> few other combinatorial interpretations.
>
> Is it indeed that sequence? If so, can we infer any interesting results
> from this connection?
>
> --
> Thanks