login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A106400 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 1's and -1's. 28
1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

See A010060, the main entry for the Thue-Morse sequence, for additional information. - N. J. A. Sloane, Aug 13 2014

a(A000069(n)) = -1; a(A001969(n)) = +1. - Reinhard Zumkeller, Apr 29 2012

Partial sums of every third terms give A005599. - Reinhard Zumkeller, May 26 2013

Fixed point of the morphism 1 --> 1,-1 and -1 --> -1,1. - Robert G. Wilson v, Apr 07 2014

Fibbinary numbers (A003714) gives the numbers n for which a(n) = A132971(n). - Antti Karttunen, May 30 2017

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Joerg Arndt, Matters Computational (The Fxtbook)

Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.

Thomas Baruchel, A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series, arXiv:1912.00452 [math.NT], 2019.

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.

Hao Fu and G.-N. Han, Computer assisted proof for Apwenian sequences related to Hankel determinants, arXiv preprint arXiv:1601.04370 [math.NT], 2016.

Philip Lafrance, Narad Rampersad, and Randy Yee, Some properties of a Rudin-Shapiro-like sequence, arXiv:1408.2277 [math.CO], 2014.

Martín Mereb, Determinants of matrices related to the Pascal triangle, arXiv:2210.12913 [math.NT], 2022.

Eric Weisstein's World of Mathematics, Thue-Morse sequence.

Wikipedia, Bell polynomials

Index entries for sequences related to binary expansion of n

FORMULA

a(n) = (-1)^A010060(n).

a(n) = (-1)^wt(n), where wt(n) is the binary weight of n, A000120(n).

G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = v^3 - 2*u*v*w + u^2*w.

G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6*u1^3 - 3*u6*u2*u1^2 + 3*u6*u2^2*u1 - u3*u2^3.

Euler transform of sequence b(n) where b(2^k) = -1 and zero otherwise.

G.f.: Product_{k>=0} (1 - x^(2^k)) = A(x) = (1-x) * A(x^2).

a(n) = B_n(-A038712(1)*0!, ..., -A038712(n)*(n-1)!)/n!, where B_n(x_1, ..., x_n) is the n-th complete Bell polynomial. See the Wikipedia link for complete Bell polynomials , and A036040 for the coefficients of these partition polynomials. - Gevorg Hmayakyan, Jul 10 2016 (edited by - Wolfdieter Lang, Aug 31 2016)

a(n) = A008836(A005940(1+n)). [Analogous to Liouville's lambda] - Antti Karttunen, May 30 2017

a(n) = (-1)^A309303(n), see the closed form (5) in the MathWorld link. - Vladimir Reshetnikov, Jul 23 2019

EXAMPLE

G.f. = 1 - x - x^2 + x^3 - x^4 + x^5 + x^6 - x^7 - x^8 + x^9 + x^10 + ...

The first 2^2 = 4 terms are 1, -1, -1, 1. Exchanging 1 and -1 gives -1, 1, 1, -1, which are a(4) through a(7). - Michael B. Porter, Jul 29 2016

MAPLE

A106400 := proc(n)

1-2*A010060(n) ;

end proc: # R. J. Mathar, Jul 22 2012

subs("0"=1, "1"=-1, StringTools:-Explode(StringTools:-ThueMorse(1000))); # Robert Israel, Sep 01 2015

# third Maple program:

a:= n-> (-1)^add(i, i=Bits[Split](n)):

seq(a(n), n=0..120); # Alois P. Heinz, Apr 13 2020

MATHEMATICA

tm[0] = 0; tm[n_?EvenQ] := tm[n/2]; tm[n_] := 1 - tm[(n-1)/2]; Table[(-1)^tm[n], {n, 0, 101}] (* Jean-François Alcover, Oct 24 2013 *)

Nest[ Flatten[# /. {1 -> {1, -1}, -1 -> {-1, 1}}] &, {1}, 7] (* Robert G. Wilson v, Apr 07 2014 *)

Table[Coefficient[Product[1 - x^(2^k), {k, 0, Log2[n + 1]}], x, n], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 11 2016 *)

PROG

(PARI) {a(n) = if( n<1, n>=0, a(n\2) * (-1)^(n%2))};

(PARI) {a(n) = my(A, m); if( n<1, n==0, m=1; A = 1 + O(x); while( m<=n, m*=2; A = subst(A, x, x^2) * (1-x)); polcoeff(A, n))};

(PARI) a(n) = { 1 - 2 * (hammingweight(n) % 2) }; \\ Gheorghe Coserea, Aug 30 2015

(PARI) apply( {A106400(n)=(-1)^hammingweight(n)}, [0..99]) \\ M. F. Hasler, Feb 07 2020

(Haskell)

import Data.List (transpose)

a106400 n = a106400_list !! n

a106400_list = 1 : concat

(transpose [map negate a106400_list, tail a106400_list])

-- Reinhard Zumkeller, Apr 29 2012

(Magma) [1-2*(&+Intseq(n, 2) mod(2)): n in [0..100]]; // Vincenzo Librandi, Sep 01 2015

(Python)

def aupto(nn):

A = [1]

while len(A) < nn+1: A += [-i for i in A]

return A[:nn+1]

print(aupto(101)) # Michael S. Branicky, Jun 26 2022

CROSSREFS

Convolution inverse of A018819.

Cf. A010060 (0 -> 1 & 1 -> -1), A000120, A000069, A001969, A003714, A005599, A038712, A005940, A008836, A132971.

Partial sums of A292118.

Sequence in context: A087960 A164660 A212159 * A112865 A114523 A130151

Adjacent sequences: A106397 A106398 A106399 * A106401 A106402 A106403

KEYWORD

sign,easy

AUTHOR

Michael Somos, May 02 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 04:29 EST 2022. Contains 358649 sequences. (Running on oeis4.)