

A010060


ThueMorse sequence: let A_k denote the first 2^k terms; then A_0 = 0 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0's and 1's.


341



0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

Also called the ThueMorse infinite word.
Fixed point of the morphism 0 > 01, 1 > 10, see example.  Joerg Arndt, Mar 12 2013
The sequence is cubefree (does not contain three consecutive identical blocks) and is overlapfree (does not contain XYXYX where X is 0 or 1 and Y is any string of 0's and 1's).
a(n) = "parity sequence" = parity of number of 1's in binary representation of n.
To construct the sequence: alternate blocks of 0's and 1's of successive lengths A003159(k)  A003159(k1), k = 1, 2, 3, ... (A003159(0) = 0). Example: since the first seven differences of A003159 are 1, 2, 1, 1, 2, 2, 2, the sequence starts with 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0.  Emeric Deutsch, Jan 10 2003
Characteristic function of A000069 (odious numbers).  Ralf Stephan, Jun 20 2003
a(n) = S2(n) mod 2, where S2(n) = sum of digits of n, n in base2 notation. There is a class of generalized ThueMorse sequences : Let Sk(n) = sum of digits of n; n in basek notation. Let F(t) be some arithmetic function. Then a(n)= F(Sk(n)) mod m is a generalized ThueMorse sequence. The classical ThueMorse sequence is the case k=2, m=2, F(t)= 1.  Ctibor O. Zizka, Feb 12 2008
More generally, the partial sums of the generalized ThueMorse sequences a(n) = F(Sk(n)) mod m are fractal, where Sk(n) is sum of digits of n, n in base k; F(t) is an arithmetic function; m integer.  Ctibor O. Zizka, Feb 25 2008
Starting with offset 1, = running sums mod 2 of the kneading sequence (A035263, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1,...); also parity of A005187: (1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19,...).  Gary W. Adamson, Jun 15 2008
Generalized ThueMorse sequences mod n (n>1) = the array shown in A141803. As n > Inf. the sequences > (1, 2, 3,...).  Gary W. Adamson, Jul 10 2008
The ThueMorse sequence for N = 3 = A053838, (sum of digits of n in base 3, mod 3): (0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2,...) = A004128 mod 3.  Gary W. Adamson, Aug 24 2008
For all positive integers k, the subsequence a(0) to a(2^k1) is identical to the subsequence a(2^k+2^(k1)) to a(2^(k+1)+2^(k1)1). That is to say, the first half of A_k is identical to the second half of B_k, and the second half of A_k is identical to the first quarter of B_{k+1}, which consists of the k/2 terms immediately following B_k.
Proof: The subsequence a(2^k+2^(k1)) to a(2^(k+1)1), the second half of B_k, is by definition formed from the subsequence a(2^(k1)) to a(2^k1), the second half of A_k, by interchanging its 0s and 1s. In turn, the subsequence a(2^(k1)) to a(2^k1), the second half of A_k, which is by definition also B_{k1}, is by definition formed from the subsequence a(0) to a(2^(k1)1), the first half of A_k, which is by definition also A_{k1}, by interchanging its 0s and 1s. Interchanging the 0s and 1s of a subsequence twice leaves it unchanged, so the subsequence a(2^k+2^(k1)) to a(2^(k+1)1), the second half of B_k, must be identical to the subsequence a(0) to a(2^(k1)1), the first half of A_k.
Also, the subsequence a(2^(k+1)) to a(2^(k+1)+2^(k1)1), the first quarter of B_{k+1}, is by definition formed from the subsequence a(0) to a(2^(k1)1), the first quarter of A_{k+1}, by interchanging its 0s and 1s. As noted above, the subsequence a(2^(k1)) to a(2^k1), the second half of A_k, which is by definition also B_{k1}, is by definition formed from the subsequence a(0) to a(2^(k1)1), which is by definition A_{k1}, by interchanging its 0s and 1s, as well. If two subsequences are formed from the same subsequence by interchanging its 0s and 1s then they must be identical, so the subsequence a(2^(k+1)) to a(2^(k+1)+2^(k1)1), the first quarter of B_{k+1}, must be identical to the subsequence a(2^(k1)) to a(2^k1), the second half of A_k.
Therefore the subsequence a(0), ..., a(2^(k1)1), a(2^(k1)),..., a(2^k1) is identical to the subsequence a(2^k+2^(k1)), ..., a(2^(k+1)1), a(2^(k+1)), ..., a(2^(k+1)+2^(k1)1), QED.
According to the German chess rules of 1929 a game of chess was drawn if the same sequence of moves was repeated three times consecutively. Euwe, see the references, proved that this rule could lead to infinite games. For his proof he reinvented the ThueMorse sequence.  Johannes W. Meijer, Feb 04 2010
"ThueMorse 0>01 & 1>10, at each stage append the previous with its complement. Start with 0, 1, 2, 3 and write them in binary. Next calculate the sum of the digits (mod 2)  that is divide the sum by 2 and use the remainder." Pickover, The Math Book.
Let s_2(n) be the sum of the base2 digits of n and epsilon(n) = (1)^s_2(n), the ThueMorse sequence, then prod(n >= 0, ((2*n+1)/(2*n+2))^epsilon(n) ) = 1/sqrt(2).  Jonathan Vos Post, Jun 06 2012
Dekking shows that the constant obtained by interpreting this sequence as a binary expansion is transcendental; see also "The Ubiquitous ProuhetThueMorse Sequence".  Charles R Greathouse IV, Jul 23 2013
Drmota, Mauduit, and Rivat proved that the subsequence a(n^2) is normalsee A228039.  Jonathan Sondow, Sep 03 2013
Although the probability of a 0 or 1 is equal, guesses predicated on the latest bit seen produce a correct match 2 out of 3 times.  Bill McEachen, Mar 13 2015


REFERENCES

A. G. M. Ahmed, AA Weaving, in Proceedings of Bridges 2013: Mathematics, Music, Art, ..., 2013; http://archive.bridgesmathart.org/2013/bridges2013263.pdf
J.P. Allouche, Lecture notes on automatic sequences, Krakow October 2013; http://ssdnm.mimuw.edu.pl/pliki/wyklady/alloucheuj.pdf
J.P. Allouche, Thue, Combinatorics on words, and conjectures inspired by the ThueMorse sequence, J. de Théorie des Nombres de Bordeaux, 27, no. 2 (2015), 375388.
J.P. Allouche and J. Shallit, The ring of kregular sequences, II, Theoret. Computer Sci., 307 (2003), 329.
J.P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 15.
J.P. Allouche and H. Cohen, "Dirichlet Series and Curious Infinite Products." Bull. London Math. Soc. 17, 531538, 1985.
F. Axel et al., Vibrational modes in a one dimensional "quasialloy": the Morse case, J. de Physique, Colloq. C3, Supp. to No. 7, Vol. 47 (Jul 1986), pp. C3181C3186; see Eq. (10).
Jason Bell, Michael Coons, and Eric Rowland, "The RationalTranscendental Dichotomy of Mahler Functions", Journal of Integer Sequences, Vol. 16 (2013), #13.2.10.
J. Berstel and J. Karhumaki, Combinatorics on words  a tutorial, Bull. EATCS, #79 (2003), pp. 178228.
B. Bollobas, The Art of Mathematics: Coffee Time in Memphis, Cambridge, 2006, p. 224.
S. Brlek, Enumeration of factors in the ThueMorse word, Discrete Applied Math., 24 (1989), 8396. doi:10.1016/0166218X(92)90274E.
Yann Bugeaud and GuoNiu Han,, A combinatorial proof of the nonvanishing of Hankel determinants of the ThueMorse sequence, Electronic Journal of Combinatorics 21(3) (2014), #P3.26.
Y. Bugeaud and M. Queffélec, On Rational Approximation of the Binary ThueMorseMahler Number, Journal of Integer Sequences, 16 (2013), #13.2.3.
J. Cooper and A. Dutle, Greedy Galois Games, Amer. Math. Mnthly, 120 (2013), 441451.
A. de Luca and S. Varricchio, Some combinatorial properties of the ThueMorse sequence and a problem in semigroups, Theoret. Comput. Sci. 63 (1989), 333348.  From N. J. A. Sloane, Jul 10 2012
F. Dejean, Sur un theoreme de Thue. J. Combinatorial Theory Ser. A 13 (1972), 9099.
F. M. Dekking, Transcendence du nombre de ThueMorse, Comptes Rendus de l'Academie des Sciences de Paris 285 (1977), pp. 157160.
F. M. Dekking, On repetitions of blocks in binary sequences. J. Combinatorial Theory Ser. A 20 (1976), no. 3, pp. 292299. MR0429728(55 #2739)
Dubickas, Artūras. On a sequence related to that of ThueMorse and its applications. Discrete Math. 307 (2007), no. 910, 10821093. MR2292537 (2008b:11086).
Fabien Durand, Julien Leroy, and Gwenaël Richomme, "Do the Properties of an Sadic Representation Determine Factor Complexity?", Journal of Integer Sequences, Vol. 16 (2013), #13.2.6.
M. Euwe, Mengentheoretische Betrachtungen Über das Schachspiel, Proceedings Koninklijke Nederlandse Akademie van Wetenschappen, Amsterdam, Vol. 32 (5): 633642, 1929. [From Johannes W. Meijer, Feb 04 2010.]
S. Ferenczi, Complexity of sequences and dynamical systems, Discrete Math., 206 (1999), 145154.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.8.
Maciej Gawron, and Maciej Ulas. "On formal inverse of the ProuhetThueMorse sequence." Discrete Mathematics 339.5 (2016): 14591470. Also arXiv:1601.04840, 2016.
W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 44194429.
G. A. Hedlund, Remarks on the work of Axel Thue on sequences, Nordisk Mat. Tid., 15 (1967), 148150.
A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149159.
Mari Huova and Juhani Karhumäki, "On Unavoidability of kabelian Squares in Pure Morphic Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.9.
B. Kitchens, Review of "Computational Ergodic Theory" by G. H. Choe, Bull. Amer. Math. Soc., 44 (2007), 147155.
Naoki Kobayashi, Kazutaka Matsuda and Ayumi Shinohara, Functional Programs as Compressed Data, http://www.kb.ecei.tohoku.ac.jp/~koba/papers/pepm2012full.pdf
Le Breton, Xavier, Linear independence of automatic formal power series. Discrete Math. 306 (2006), no. 15, 17761780.
M. Lothaire, Combinatorics on Words. AddisonWesley, Reading, MA, 1983, p. 23.
Mauduit, Christian. Multiplicative properties of the ThueMorse sequence. Period. Math. Hungar. 43 (2001), no. 12, 137153. MR1830572 (2002i:11081)
Mignosi, F.; Restivo, A.; Sciortino, M. Words and forbidden factors. WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 12, 99117. MR1872445 (2002m:68096)  From N. J. A. Sloane, Jul 10 2012
M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22 (1921), 84100.
K. Nakano, Shall We Juggle, Coinductively?, in Certified Programs and Proofs, Lecture Notes in Computer Science Volume 7679, 2012, pp. 160172, DOI 10.1007/9783642353086_14.
H. D. Nguyen, A mixing of ProuhetThueMorse sequences and Rademacher functions, http://www.rowan.edu/colleges/csm/departments/math/facultystaff/nguyen/papers/mixingptmrademacher.pdf, 2014
C. A. Pickover, Wonders of Numbers, Adventures in Mathematics, Mind and Meaning, Chapter 17, 'The Pipes of Papua,' Oxford University Press, Oxford, England, 2000, pages 34  38.
C. A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 60.
Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 316.
Narad Rampersad and Elise Vaslet, "On Highly Repetitive and Power Free Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.7.
G. Richomme, K. Saari, L. Q. Zamboni, Abelian complexity in minimal subshifts, J. London Math. Soc. 83(1) (2011) 7995.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence  see "List of Sequences" in Vol. 2.
M. Rigo, P. Salimov, and E. Vandomme, "Some Properties of Abelian Return Words", Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
Benoit Rittaud, Elise Janvresse, Emmanuel Lesigne and JeanChristophe Novelli, Quand les maths se font discrètes, Le Pommier, 2008 (ISBN 9782746503700).
A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.
Luke Schaeffer, Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
Shallit, J. O. "On Infinite Products Associated with Sums of Digits." J. Number Th. 21, 128134, 1985.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 890.


LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..16383
A. Aksenov, The Newman phenomenon and Lucas sequence, arXiv preprint arXiv:1108.5352 [math.NT], 20112012.
Joerg Arndt, Matters Computational (The Fxtbook), p.44
J.P. Allouche, Series and infinite products related to binary expansions of integers
J.P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, A sequence related to that of ThueMorse, Discrete Math., 139 (1995), 455461.
J.P. Allouche and M. Mendes France, Automata and Automatic Sequences.
J.P. Allouche and J. Shallit, The Ring of kregular Sequences, II
J.P. Allouche and Jeffrey Shallit, The Ubiquitous ProuhetThueMorse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, SpringerVerlag, 1999, pp. 116.
Ricardo Astudillo, On a Class of ThueMorse Type Sequences, J. Integer Seqs., Vol. 6, 2003.
M. Baake, U. Grimm, J. Nilsson, Scaling of the ThueMorse diffraction measure, arXiv preprint arXiv:1311.4371 [mathph], 2013.
Jean Berstel, Home Page
Bertazzon J.F., Resolution of an integral equation with the ThueMorse sequence, arXiv:1201.2502v1 [math.CO], Jan 12, 2012.
F. Michel Dekking, Pure morphic sequences and their standard forms, arXiv:1509.00260 [math.CO], 2015.
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191215.
M. Drmota, C. Mauduit, J. Rivat, The ThueMorse Sequence Along The Squares is Normal, Abstract, ÖMGDMV Congress, 2013.
J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams.
A. S. Fraenkel, Home Page
A. S. Fraenkel, New games related to old and new sequences, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
Michael Gilleland, Some SelfSimilar Integer Sequences
Daniel Goc, Luke Schaeffer and Jeffrey Shallit, The Subword Complexity of kAutomatic Sequences is kSynchronized, arXiv 1206.5352 [cs.FL], Jun 28 2012.
Dimitri Hendriks, Frits G. W. Dannenberg, Jorg Endrullis, Mark Dow and Jan Willem Klop, Arithmetic SelfSimilarity of Infinite Sequences, arXiv preprint 1201.3786 [math.CO], 2012.
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi  Myths and Maths, Birkhäuser 2013. See page 79. Book's website
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Philip Lafrance, Narad Rampersad, Randy Yee, Some properties of a RudinShapirolike sequence, arXiv:1408.2277 [math.CO], 2014.
C. Mauduit, J. Rivat, La somme des chiffres des carres, Acta Mathem. 203 (1) (2009) 107148.
M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22 (1921), 84100.
A. Parreau, M. Rigo, E. Rowland, E. Vandomme, A new approach to the 2regularity of the labelian complexity of 2automatic sequences, arXiv preprint arXiv:1405.3532 [cs.FL], 2014.
C. A. Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," Zentralblatt review
R. Schroeppel and R. W. Gosper, HACKMEM #122 (1972).
N. J. A. Sloane, The first 1000 terms as a string
L. Spiegelhofer, Normality of the ThueMorse Sequence along PiatetskiShapiro sequences, Quart. J. Math. 66 (3) (2015)
Eric Weisstein's World of Mathematics, ThueMorse Sequence
Eric Weisstein's World of Mathematics, ThueMorse Constant
Eric Weisstein's World of Mathematics, Parity
J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, Contextfree coalgebras, 2013;
Index entries for "core" sequences
Index entries for sequences related to binary expansion of n
Index entries for characteristic functions


FORMULA

a(2n) = a(n), a(2n+1) = 1  a(n), a(0) = 0. Also, a(k+2^m) = 1  a(k) if 0 <= k < 2^m.
If n = Sum b_i*2^i is the binary expansion of n then a(n) = Sum b_i (mod 2).
Let S(0) = 0 and for k >= 1, construct S(k) from S(k1) by mapping 0 > 01 and 1 > 10; sequence is S(infinity).
G.f.: (1/(1x)  product_{k >= 0} 1  x^(2^k))/2.  Benoit Cloitre, Apr 23 2003
a(0) = 0, a(n) = (n+a(floor(n/2))) mod 2; also a(0) = 0, a(n) = (na(floor(n/2))) mod 2.  Benoit Cloitre, Dec 10 2003
a(n) = 1 + sum(k = 0, n, binomial(n, k){mod 2}) {mod 3} = 1 + A001316(n) {mod 3}.  Benoit Cloitre, May 09 2004
Let b(1) = 1 and b(n) = b(ceiling(n/2))  b(floor(n/2)) then a(n1) = (1/2)*(1b(2n1)).  Benoit Cloitre, Apr 26 2005
a(n) = 1  A010059(n) = A001285(n)  1.  Ralf Stephan, Jun 20 2003
a(n) = A001969(n)  2n.  Franklin T. AdamsWatters, Aug 28 2006
a(n) = A115384(n)  A115384(n1) for n > 0.  Reinhard Zumkeller, Aug 26 2007
For n >= 0, a(A004760(n+1)) = 1  a(n).  Vladimir Shevelev, Apr 25 2009
a(A160217(n)) = 1  a(n).  Vladimir Shevelev, May 05 2009
A010060(n) == A000069(n)(mod 2).  Robert G. Wilson v, Jan 18 2012
a(n) = A000035(A000120(n)).  Omar E. Pol, Oct 26 2013
a(n) = A000035(A193231(n)).  Antti Karttunen, Dec 27 2013
a(n) + A181155(n1) = 2n for n >= 1.  Clark Kimberling, Oct 06 2014


EXAMPLE

The evolution starting at 0 is:
.0
.0, 1
.0, 1, 1, 0
.0, 1, 1, 0, 1, 0, 0, 1
.0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0
.0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1
.......
A_2 = 0 1 1 0, so B_2 = 1 0 0 1 and A_3 = A_2 B_2 = 0 1 1 0 1 0 0 1.
From Joerg Arndt, Mar 12 2013: (Start)
The first steps of the iterated substitution are
Start: 0
Rules:
0 > 01
1 > 10

0: (#=1)
0
1: (#=2)
01
2: (#=4)
0110
3: (#=8)
01101001
4: (#=16)
0110100110010110
5: (#=32)
01101001100101101001011001101001
6: (#=64)
0110100110010110100101100110100110010110011010010110100110010110
(End)
From Omar E. Pol, Oct 28 2013: (Start)
Written as an irregular triangle in which row lengths is A011782, the sequence begins:
0;
1;
1,0;
1,0,0,1;
1,0,0,1,0,1,1,0;
1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1;
1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0;
It appears that: row j lists the first A011782(j) terms of A010059, with j >= 0; row sums give A166444 which is also 0 together with A011782; right border gives A000035.
(End)


MAPLE

s := proc(k) local i, ans; ans := [ 0, 1 ]; for i from 0 to k do ans := [ op(ans), op(map(n>(n+1) mod 2, ans)) ] od; return ans; end; t1 := s(6); A010060 := n>t1[n]; # s(k) gives first 2^(k+2) terms.
a := proc(k) b := [0]: for n from 1 to k do b := subs({0=[0, 1], 1=[1, 0]}, b) od: b; end; # a(k), after the removal of the brackets, gives the first 2^k terms. # Example: a(3); gives [[[[0, 1], [1, 0]], [[1, 0], [0, 1]]]]
A010060:=proc(n) local n2: n2:=convert(n, base, 2): sum(n2[j], j=1..nops(n2)) mod 2; end:
seq(A010060(n), n=0..104); # Emeric Deutsch, Mar 19 2005
map(``, convert(StringTools[ThueMorse](1000), bytes), 48); # Robert Israel, Sep 22 2014


MATHEMATICA

Table[ If[ OddQ[ Count[ IntegerDigits[n, 2], 1]], 1, 0], {n, 0, 100}];
mt = 0; Do[ mt = ToString[mt] <> ToString[(10^(2^n)  1)/9  ToExpression[mt] ], {n, 0, 6} ]; Prepend[ RealDigits[ N[ ToExpression[mt], 2^7] ] [ [1] ], 0]
Mod[ Count[ #, 1 ]& /@Table[ IntegerDigits[ i, 2 ], {i, 0, 2^7  1} ], 2 ] (* Harlan J. Brothers, Feb 05 2005 *)
Nest[ Flatten[ # /. {0 > {0, 1}, 1 > {1, 0}}] &, {0}, 7] (* Robert G. Wilson v Sep 26 2006 *)
a[n_] := If[n == 0, 0, If[Mod[n, 2] == 0, a[n/2], 1  a[(n  1)/2]]] (* Ben Branman, Oct 22 2010 *)
a[n_] := Mod[Length[FixedPointList[BitAnd[#, #  1] &, n]], 2] (* Jan Mangaldan, Jul 23 2015 *)


PROG

(Haskell)
a010060 n = a010060_list !! n
a010060_list =
0 : interleave (complement a010060_list) (tail a010060_list)
where complement = map (1  )
interleave (x:xs) ys = x : interleave ys xs
 Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 29 2003
 Edited by Reinhard Zumkeller, Oct 03 2012
(PARI) a(n)=if(n<1, 0, sum(k=0, length(binary(n))1, bittest(n, k))%2)
(PARI) a(n)=if(n<1, 0, subst(Pol(binary(n)), x, 1)%2)
(PARI) { default(realprecision, 6100); x=0.0; m=20080; for (n=1, m1, x=x+x; x=x+sum(k=0, length(binary(n))1, bittest(n, k))%2); x=2*x/2^m; for (n=0, 20000, d=floor(x); x=(xd)*2; write("b010060.txt", n, " ", d)); } \\ Harry J. Smith, Apr 28 2009
(PARI) a(n)=hammingweight(n)%2 \\ Charles R Greathouse IV, Mar 22 2013
(Python)
A010060_list = [0]
for _ in range(14):
A010060_list += [1d for d in A010060_list] # Chai Wah Wu, Mar 04 2016


CROSSREFS

Cf. A001285 (for 1, 2 version), A010059 (for 1, 0 version), A106400 (for +1, 1 version), A048707. A010060(n)=A000120(n) mod 2.
Cf. A007413, A080813, A080814, A036581, A108694. See also the Thue (or Roth) constant A014578, also A014571.
Cf. also A001969, A035263, A005187, A115384, A132680, A141803, A104248, A193231.
Backward first differences give A029883.
Cf. A004128, A053838, A059448, A171900, A161916, A214212, A005942 (subword complexity), A010693 (Abelian complexity), A225186 (squares), A228039 (a(n^2)).
Sequence in context: A029691 A156595 A143222 * A118247 A122257 A129950
Adjacent sequences: A010057 A010058 A010059 * A010061 A010062 A010063


KEYWORD

nonn,core,easy,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Additional comments from Robert G. Wilson v, Dec 29 2000


STATUS

approved



