login
The OEIS is supported by the many generous donors to the OEIS 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. 52
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
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.
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.
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
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
(Python)
def A010059(n): return n.bit_count()&1^1 # Chai Wah Wu, Mar 01 2023
CROSSREFS
Cf. A001285 (1, 2 version), A010060 (0, 1 version), A106400 (+1, -1 version), A059448 (with reversed subsections).
Cf. also A000069, A026147, A159481.
Sequence in context: A285252 A076404 A317961 * A143580 A011749 A277450
KEYWORD
nonn,easy
AUTHOR
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 March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)