%I M0193 N0071 #136 Mar 01 2024 11:07:55
%S 1,2,2,1,2,1,1,2,2,1,1,2,1,2,2,1,2,1,1,2,1,2,2,1,1,2,2,1,2,1,1,2,2,1,
%T 1,2,1,2,2,1,1,2,2,1,2,1,1,2,1,2,2,1,2,1,1,2,2,1,1,2,1,2,2,1,2,1,1,2,
%U 1,2,2,1,1,2,2,1,2,1,1,2,1,2,2,1,2,1,1,2,2,1,1,2,1,2,2,1,1,2,2,1,2,1
%N 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 2's.
%C Or, follow a(0), ..., a(2^k-1) by its complement.
%C Equals limiting row of A161175. - _Gary W. Adamson_, Jun 05 2009
%C Parse A010060 into consecutive pairs: (01, 10, 10, 01, 10, 01, ...); then apply the rules: (01 -> 1; 10 ->2), obtaining (1, 2, 2, 1, 2, 1, 1, ...). - _Gary W. Adamson_, Oct 25 2010
%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 15.
%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
%D W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
%D M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.
%D A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Seiichi Manyama, <a href="/A001285/b001285.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1023 from T. D. Noe)
%H J.-P. Allouche and Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps">The Ubiquitous Prouhet-Thue-Morse Sequence</a>, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
%H F. Axel et al., <a href="https://hal.archives-ouvertes.fr/jpa-00225729">Vibrational modes in a one dimensional "quasi-alloy": the Morse case</a>, J. de Physique, Colloq. C3, Supp. to No. 7, Vol. 47 (Jul 1986), pp. C3-181-C3-186; see Eq. (10).
%H Scott Balchin and Dan Rust, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Rust/rust3.html">Computations for Symbolic Substitutions</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H J. D. Currie, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Currie/currie7.html">The Least Self-Shuffle of the Thue-Morse Sequence</a>, J. Int. Seq. 17 (2014) # 14.10.2.
%H Françoise Dejean, <a href="http://dx.doi.org/10.1016/0097-3165(72)90011-8">Sur un Théorème de Thue</a>, J. Combinatorial Theory, vol. 13 A, iss. 1 (1972) 90-99.
%H F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H Arturas Dubickas, <a href="http://dx.doi.org/10.1016/j.jnt.2005.07.004">On the distance from a rational power to the nearest integer</a>, Journal of Number Theory, Volume 117, Issue 1, March 2006, Pages 222-239.
%H Arturas Dubickas, <a href="http://dx.doi.org/10.1016/j.disc.2006.08.001">On a sequence related to that of Thue-Morse and its applications</a>, Discrete Math. 307 (2007), no. 9-10, 1082--1093. MR2292537 (2008b:11086).
%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>
%H G. A. Hedlund, <a href="https://www.jstor.org/stable/24525014">Remarks on the work of Axel Thue on sequences</a>, Nordisk Mat. Tid., 15 (1967), 148-150.
%H A. Hof, O. Knill and B. Simon, <a href="http://inis.iaea.org/search/search.aspx?orig_q=RN:27016845">Singular continuous spectrum for palindromic Schroedinger operators</a>, Commun. Math. Phys. 174 (1995), 149-159.
%H Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.
%H M. Morse, <a href="http://dx.doi.org/10.1090/S0002-9947-1921-1501161-8">Recurrent geodesics on a surface of negative curvature</a>, Trans. Amer. Math. Soc., 22 (1921), 84-100.
%H G. Siebert, <a href="/A001285/a001285_1.pdf">Letter to N. J. A. Sloane, Sept. 1977</a>
%H N. J. A. Sloane, <a href="/A001285/a001285.txt">The first 1000 terms as a string</a>
%H N. J. A. Sloane, <a href="/A001149/a001149.pdf">Handwritten notes on Self-Generating Sequences, 1970</a> (note that A1148 has now become A005282)
%H N. J. A. Sloane, P. Flor, L. F. Meyers, G. A. Hedlund. M. Gardner, <a href="/A001285/a001285.pdf">Collection of documents and notes related to A1285, A3270, A3324</a>
%H S. Wolfram, <a href="http://www.wolframscience.com/nksonline/page-889c-text">Source for short Thue-Morse generating code</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>
%F a(2n) = a(n), a(2n+1) = 3 - a(n), a(0) = 1. Also, a(k+2^m) = 3 - a(k) if 0 <= k < 2^m.
%F a(n) = 1 + A010060(n).
%F a(n) = 2 - A010059(n) = 1/2*(3 - (-1)^A000120(n)). - _Ralf Stephan_, Jun 20 2003
%F a(n) = (Sum{k=0..n} binomial(n, k) mod 2) mod 3 = A001316(n) mod 3. - _Benoit Cloitre_, May 09 2004
%F G.f.: (3/(1 - x) - Product_{k>=0} (1 - x^(2^k)))/2. - _Ilya Gutkovskiy_, Apr 03 2019
%p A001285 := proc(n) option remember; if n=0 then 1 elif n mod 2 = 0 then A001285(n/2) else 3-A001285((n-1)/2); fi; end;
%p s := proc(k) local i, ans; ans := [ 1,2 ]; for i from 0 to k do ans := [ op(ans),op(map(n->if n=1 then 2 else 1 fi, ans)) ] od; RETURN(ans); end; t1 := s(6); A001285 := n->t1[n]; # s(k) gives first 2^(k+2) terms
%t Nest[ Flatten@ Join[#, # /. {1 -> 2, 2 -> 1}] &, {1}, 7] (* _Robert G. Wilson v_, Feb 26 2005 *)
%t a[n_] := Mod[Sum[Mod[Binomial[n, k], 2], {k, 0, n}], 3]; Table[a[n], {n, 0, 101}] (* _Jean-François Alcover_, Jul 02 2019 *)
%t ThueMorse[Range[0,120]]+1 (* _Harvey P. Dale_, May 07 2021 *)
%o (PARI) a(n)=1+subst(Pol(binary(n)),x,1)%2
%o (PARI) a(n)=sum(k=0,n,binomial(n,k)%2)%3
%o (PARI) a(n)=hammingweight(n)%2+1 \\ _Charles R Greathouse IV_, Mar 26 2013
%o (Haskell)
%o a001285 n = a001285_list !! n
%o a001285_list = map (+ 1) a010060_list
%o -- _Reinhard Zumkeller_, Oct 03 2012
%o (Python)
%o from itertools import islice
%o def A001285_gen(): # generator of terms
%o yield 1
%o blist = [1]
%o while True:
%o c = [3-d for d in blist]
%o blist += c
%o yield from c
%o A001285_list = list(islice(A001285_gen(),30)) # _Chai Wah Wu_, Nov 13 2022
%o (Python)
%o def A001285(n): return 2 if n.bit_count()&1 else 1 # _Chai Wah Wu_, Mar 01 2023
%Y Cf. A010060 for 0, 1 version, which is really the main entry for this sequence; also A003159. A225186 (squares).
%Y A026465 gives run lengths.
%Y Cf. A010059 (1, 0 version).
%Y Cf. A161175. - _Gary W. Adamson_, Jun 05 2009
%Y Cf. A026430 (partial sums).
%Y Boustrophedon transforms: A230958, A029885.
%K nonn,easy,core,nice
%O 0,2
%A _N. J. A. Sloane_