cp's OEIS Frontend

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.

%I A106400 #133 Dec 18 2023 08:27:52
%S A106400 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,
%T A106400 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,
%U A106400 -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
%N 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.
%C A106400 See A010060, the main entry for the Thue-Morse sequence, for additional information. - _N. J. A. Sloane_, Aug 13 2014
%C A106400 a(A000069(n)) = -1; a(A001969(n)) = +1. - _Reinhard Zumkeller_, Apr 29 2012
%C A106400 Partial sums of every third terms give A005599. - _Reinhard Zumkeller_, May 26 2013
%C A106400 Fixed point of the morphism 1 --> 1,-1 and -1 --> -1,1. - _Robert G. Wilson v_, Apr 07 2014
%C A106400 Fibbinary numbers (A003714) gives the numbers n for which a(n) = A132971(n). - _Antti Karttunen_, May 30 2017
%H A106400 Reinhard Zumkeller, <a href="/A106400/b106400.txt">Table of n, a(n) for n = 0..10000</a>
%H A106400 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>
%H A106400 Thomas Baruchel, <a href="https://doi.org/10.1007/s42979-019-0049-1">Flattening Karatsuba's Recursion Tree into a Single Summation</a>, SN Computer Science (2020) Vol. 1, Article No. 48.
%H A106400 Thomas Baruchel, <a href="https://arxiv.org/abs/1912.00452">A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series</a>, arXiv:1912.00452 [math.NT], 2019.
%H A106400 Yann Bugeaud and Guo-Niu Han, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p26/0">A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence</a>, Electronic Journal of Combinatorics 21(3) (2014), #P3.26.
%H A106400 Hao Fu and G.-N. Han, <a href="https://arxiv.org/abs/1601.04370">Computer assisted proof for Apwenian sequences related to Hankel determinants</a>, arXiv preprint arXiv:1601.04370 [math.NT], 2016.
%H A106400 Philip Lafrance, Narad Rampersad, and Randy Yee, <a href="http://arxiv.org/abs/1408.2277">Some properties of a Rudin-Shapiro-like sequence</a>, arXiv:1408.2277 [math.CO], 2014.
%H A106400 Martín Mereb, <a href="https://arxiv.org/abs/2210.12913">Determinants of matrices related to the Pascal triangle</a>, arXiv:2210.12913 [math.NT], 2022.
%H A106400 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Thue-MorseSequence.html">Thue-Morse sequence</a>.
%H A106400 Wikipedia, <a href="https://en.wikipedia.org/wiki/Bell_polynomials">Bell polynomials</a>
%H A106400 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A106400 a(n) = (-1)^A010060(n).
%F A106400 a(n) = (-1)^wt(n), where wt(n) is the binary weight of n, A000120(n).
%F A106400 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.
%F A106400 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.
%F A106400 Euler transform of sequence b(n) where b(2^k) = -1 and zero otherwise.
%F A106400 G.f.: Product_{k>=0} (1 - x^(2^k)) = A(x) = (1-x) * A(x^2).
%F A106400 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)
%F A106400 a(n) = A008836(A005940(1+n)). [Analogous to Liouville's lambda] - _Antti Karttunen_, May 30 2017
%F A106400 a(n) = (-1)^A309303(n), see the closed form (5) in the MathWorld link. - _Vladimir Reshetnikov_, Jul 23 2019
%e A106400 G.f. = 1 - x - x^2 + x^3 - x^4 + x^5 + x^6 - x^7 - x^8 + x^9 + x^10 + ...
%e A106400 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
%p A106400 A106400 := proc(n)
%p A106400         1-2*A010060(n) ;
%p A106400 end proc: # _R. J. Mathar_, Jul 22 2012
%p A106400 subs("0"=1,"1"=-1, StringTools:-Explode(StringTools:-ThueMorse(1000))); # _Robert Israel_, Sep 01 2015
%p A106400 # third Maple program:
%p A106400 a:= n-> (-1)^add(i, i=Bits[Split](n)):
%p A106400 seq(a(n), n=0..120);  # _Alois P. Heinz_, Apr 13 2020
%t A106400 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 *)
%t A106400 Nest[ Flatten[# /. {1 -> {1, -1}, -1 -> {-1, 1}}] &, {1}, 7] (* _Robert G. Wilson v_, Apr 07 2014 *)
%t A106400 Table[Coefficient[Product[1 - x^(2^k), {k, 0, Log2[n + 1]}], x, n], {n, 0, 20}] (* _Vladimir Reshetnikov_, Nov 11 2016 *)
%t A106400 (-1)^ThueMorse[Range[0,100]] (* _Paolo Xausa_, Dec 18 2023 *)
%o A106400 (PARI) {a(n) = if( n<1, n>=0, a(n\2) * (-1)^(n%2))};
%o A106400 (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))};
%o A106400 (PARI) a(n) = { 1 - 2 * (hammingweight(n) % 2) };  \\ _Gheorghe Coserea_, Aug 30 2015
%o A106400 (PARI) apply( {A106400(n)=(-1)^hammingweight(n)}, [0..99]) \\ _M. F. Hasler_, Feb 07 2020
%o A106400 (Haskell)
%o A106400 import Data.List (transpose)
%o A106400 a106400 n = a106400_list !! n
%o A106400 a106400_list =  1 : concat
%o A106400    (transpose [map negate a106400_list, tail a106400_list])
%o A106400 -- _Reinhard Zumkeller_, Apr 29 2012
%o A106400 (Magma) [1-2*(&+Intseq(n,2) mod(2)): n in [0..100]]; // _Vincenzo Librandi_, Sep 01 2015
%o A106400 (Python)
%o A106400 def aupto(nn):
%o A106400     A = [1]
%o A106400     while len(A) < nn+1: A += [-i for i in A]
%o A106400     return A[:nn+1]
%o A106400 print(aupto(101)) # _Michael S. Branicky_, Jun 26 2022
%o A106400 (Python)
%o A106400 def A106400(n): return -1 if n.bit_count()&1 else 1 # _Chai Wah Wu_, Mar 01 2023
%Y A106400 Convolution inverse of A018819.
%Y A106400 Cf. A010060 (0 -> 1 & 1 -> -1), A000120, A000069, A001969, A003714, A005599, A038712, A005940, A008836, A132971.
%Y A106400 Partial sums of A292118.
%K A106400 sign,easy
%O A106400 0,1
%A A106400 _Michael Somos_, May 02 2005