login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 48
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

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)

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.

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

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

EXAMPLE

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

...........

MAPLE

A010059 := n->1-A010060(n);

map(t->49-t, convert(StringTools[ThueMorse](1000), bytes)); # Robert Israel, Feb 02 2016

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

PROG

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

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

(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

CROSSREFS

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

Cf. also A000069, A026147, A159481.

Cf. A001969, A143579.

Sequence in context: A285252 A076404 A317961 * A143580 A011749 A277450

Adjacent sequences:  A010056 A010057 A010058 * A010060 A010061 A010062

KEYWORD

nonn,easy

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 17:21 EDT 2021. Contains 348065 sequences. (Running on oeis4.)