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!)
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)
64
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Or, follow a(0), ..., a(2^k-1) by its complement.

Equals limiting row of A161175. - Gary W. Adamson, Jun 05 2009

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

REFERENCES

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 15.

G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.

M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.

A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1023 from T. D. Noe)

J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.

F. Axel et al., Vibrational modes in a one dimensional "quasi-alloy": the Morse case, J. de Physique, Colloq. C3, Supp. to No. 7, Vol. 47 (Jul 1986), pp. C3-181-C3-186; see Eq. (10).

Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.

J. D. Currie, The Least Self-Shuffle of the Thue-Morse Sequence, J. Int. Seq. 17 (2014) # 14.10.2.

Francoise Dejean, Sur un Theoreme de Thue, J. Combinatorial Theory, vol. 13 A, iss. 1 (1972) 90-99.

F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.

Arturas Dubickas, On the distance from a rational power to the nearest integer, Journal of Number Theory, Volume 117, Issue 1, March 2006, Pages 222-239.

Arturas Dubickas, On a sequence related to that of Thue-Morse and its applications, Discrete Math. 307 (2007), no. 9-10, 1082--1093. MR2292537 (2008b:11086).

Michael Gilleland, Some Self-Similar Integer Sequences

G. A. Hedlund, Remarks on the work of Axel Thue on sequences, Nordisk Mat. Tid., 15 (1967), 148-150.

A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149-159.

Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.

M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22 (1921), 84-100.

G. Siebert, Letter to N. J. A. Sloane, Sept. 1977

N. J. A. Sloane, The first 1000 terms as a string

N. J. A. Sloane, Handwritten notes on Self-Generating Sequences, 1970 (note that A1148 has now become A005282)

N. J. A. Sloane, P. Flor, L. F. Meyers, G. A. Hedlund. M. Gardner, Collection of documents and notes related to A1285, A3270, A3324

S. Wolfram, Source for short Thue-Morse generating code

Index entries for "core" sequences

Index entries for sequences that are fixed points of mappings

FORMULA

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.

a(n) = 1 + A010060(n).

a(n) = 2 - A010059(n) = 1/2*(3 - (-1)^A000120(n)). - Ralf Stephan, Jun 20 2003

a(n) = (Sum{k=0..n} binomial(n, k) mod 2) mod 3 = A001316(n) mod 3. - Benoit Cloitre, May 09 2004

G.f.: (3/(1 - x) - Product_{k>=0} (1 - x^(2^k)))/2. - Ilya Gutkovskiy, Apr 03 2019

MAPLE

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;

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

MATHEMATICA

Nest[ Flatten@ Join[#, # /. {1 -> 2, 2 -> 1}] &, {1}, 7] (* Robert G. Wilson v, Feb 26 2005 *)

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 *)

ThueMorse[Range[0, 120]]+1 (* Harvey P. Dale, May 07 2021 *)

PROG

(PARI) a(n)=1+subst(Pol(binary(n)), x, 1)%2

(PARI) a(n)=sum(k=0, n, binomial(n, k)%2)%3

(PARI) a(n)=hammingweight(n)%2+1 \\ Charles R Greathouse IV, Mar 26 2013

(Haskell)

a001285 n = a001285_list !! n

a001285_list = map (+ 1) a010060_list

-- Reinhard Zumkeller, Oct 03 2012

(Python)

from itertools import islice

def A001285_gen(): # generator of terms

yield 1

blist = [1]

while True:

c = [3-d for d in blist]

blist += c

yield from c

A001285_list = list(islice(A001285_gen(), 30)) # Chai Wah Wu, Nov 13 2022

CROSSREFS

Cf. A010060 for 0, 1 version, which is really the main entry for this sequence; also A003159. A225186 (squares).

A026465 gives run lengths.

Cf. A010059 (1, 0 version).

Cf. A161175. - Gary W. Adamson, Jun 05 2009

Cf. A026430 (partial sums).

Boustrophedon transforms: A230958, A029885.

Sequence in context: A088569 A246144 A192763 * A088424 A317960 A270642

Adjacent sequences: A001282 A001283 A001284 * A001286 A001287 A001288

KEYWORD

nonn,easy,core,nice,changed

AUTHOR

N. J. A. Sloane

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 November 26 21:15 EST 2022. Contains 358362 sequences. (Running on oeis4.)