A010059 Another version of the 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 0's and 1's.

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, 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, 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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Characteristic function of A001969 (evil numbers). - Ralf Stephan, Jun 20 2003

From Gary W. Adamson, Aug 24 2008: (Start)

Parity of A143579 (Odious numbers (A000069) interleaved with Evil numbers (A001969)).

Two conjectures: If n is even, the ratio of 1's to 0's = 1:1.

There are no three adjacent terms of the same parity. (End)

Conjecture (verified for the first 280000 entries): this is the characteristic function of A001969. - R. J. Mathar, Sep 05 2008

From Michel Dekking, Jan 05 2021: (Start)

Proof of these three conjectures: the first two follow directly from the third, because the sequence A010059 is the binary complement of the Thue-Morse sequence A010060.

For the third conjecture: the odious and evil numbers occur as quadruples EOOE and OEEO, simply by their definition. To obtain the mod 2 version of the interleave of the odious and evil numbers we therefore have to apply a transformation

EOOE -> OEOE, OEEO -> OEOE to these quadruples.

But this changes the parities from the corresponding 4n, 4n+1, 4n+2, 4n+3 quadruples from 0101 to 1001 in the first case, and from 0101 to 0110 in the second case. Since the quadruples EOOE and OEEO occur in a Thue Morse pattern, then also the quadruples 1001 and 0110 occur in a Thue Morse pattern, finishing the proof.

(End)

Examples

			The evolution starting at 1 is:
.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
...........
		

References

• 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.

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• 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.
• Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
• 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.
• 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.
• Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
• H. M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22 (1921), 84-100.
• Stephen Wolfram, A New Kind Of Science | Online.
• Index entries for sequences related to binary expansion of n
• Index entries for characteristic functions

Crossrefs

Cf. A001285 (1, 2 version), A010060 (0, 1 version), A106400 (+1, -1 version), A059448 (with reversed subsections).

Cf. also A000069, A026147, A159481.

Cf. A000120, A001969, A143579.

Programs

Haskell

a010059 = (1 -) . a010060  -- Reinhard Zumkeller, Feb 04 2013

Maple

A010059 := n->1-A010060(n);
map(t->49-t,convert(StringTools[ThueMorse](1000),bytes)); # Robert Israel, Feb 02 2016
# second Maple program:
a := n -> ifelse(type(add(convert(n, base, 2)), even), 1, 0):
seq(a(n), n = 0 .. 104); # Peter Luschny, Mar 11 2024

Mathematica

Mod[ CoefficientList[Series[(1 + Sqrt[(1 - 3x)/(1 + x)])/(2(1 + x)), {x, 0, 111}], x], 2] (* Stephan Wolfram *)
CoefficientList[ Series[1/(1 - x) + Product[1 - x^2^k, {k, 0, 10}], {x, 0, 111}]/2, x] (* Robert G. Wilson v, Jul 16 2004 *)
Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {1}, 7] (* Robert G. Wilson v Sep 26 2006 *)
od = Select[ Range[0, 129], OddQ@ DigitCount[ #, 2, 1] &]; ev = Select[ Range[0, 129], EvenQ@ DigitCount[ #, 2, 1] &]; Mod[ Flatten@ Transpose[{od, ev}], 2] (* Robert G. Wilson v, Apr 14 2009 *)
Nest[ Join[ #, Mod[2# + 1, 3]] &, {1}, 7] (* Robert G. Wilson v, Jul 27 2014 *)
{{1}}~Join~SubstitutionSystem[{0 -> {0, 1}, 1 -> {1, 0}}, {0}, 6] // Flatten (* Michael De Vlieger, Aug 15 2016, Version 10.2 *)
1 - ThueMorse[Range[0, 100]] (* Paolo Xausa, Oct 25 2024 *)

PARI

a(n)=!(hammingweight(n)%2); \\ Charles R Greathouse IV, Mar 29 2013

Python

def A010059(n): return n.bit_count()&1^1 # Chai Wah Wu, Mar 01 2023

R

maxrow <- 8 # by choice
b01 <- 0
for(m in 0:maxrow) for(k in 0:(2^m-1)){
b01[2^(m+1)+    k] <-   b01[2^m+k]
b01[2^(m+1)+2^m+k] <- 1-b01[2^m+k]
}
(b01 <- c(1,b01))
# Yosu Yurramendi, Apr 10 2017

Formula

G.f.: (1/2) * (1/(1-x) + Product_{k>=0} (1 - x^2^k)). - Ralf Stephan, Jun 20 2003

a(n) = A143579(n) mod 2. - Gary W. Adamson, Aug 24 2008

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

a(n) = A159481(n+1) - A159481(n). - Reinhard Zumkeller, Apr 16 2009

a(n) + A026147(n-1) = 2n for n >= 1. - Clark Kimberling, Oct 06 2014

a(n) = A000069(n+1) (mod 2). - John M. Campbell, Jun 30 2016

a(n) = A059448(A054429(n)) = (A106400(n)+1)/2 = (1+A008836(A005940(1+n)))/2. - Antti Karttunen, May 30 2017

If A(n)=(a(0),a(2),...,a(2^n-1)), then A(n+1)=(A(n),1-A(n)). - Arie Bos, Jul 27 2022

a(n) = (1 + (-1)^A000120(n))/2. - Lorenzo Sauras Altuzarra, Mar 10 2024