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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001285 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.
(Formerly M0193 N0071)
65

%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_

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 March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)