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.

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• core
• nice

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.
• Françoise Dejean, Sur un Théorème 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

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.

Programs

Haskell

a001285 n = a001285_list !! n
a001285_list = map (+ 1) a010060_list
-- Reinhard Zumkeller, Oct 03 2012

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

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

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

Python

def A001285(n): return 2 if n.bit_count()&1 else 1 # Chai Wah Wu, Mar 01 2023

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