|
%I #119 Mar 27 2024 10:44:38
%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,
%T 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,
%U 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
%N 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.
%C Characteristic function of A001969 (evil numbers). - _Ralf Stephan_, Jun 20 2003
%C From _Gary W. Adamson_, Aug 24 2008: (Start)
%C Parity of A143579 (Odious numbers (A000069) interleaved with Evil numbers (A001969)).
%C Two conjectures: If n is even, the ratio of 1's to 0's = 1:1.
%C There are no three adjacent terms of the same parity. (End)
%C Conjecture (verified for the first 280000 entries): this is the characteristic function of A001969. - _R. J. Mathar_, Sep 05 2008
%C From _Michel Dekking_, Jan 05 2021: (Start)
%C 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.
%C 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
%C EOOE -> OEOE, OEEO -> OEOE to these quadruples.
%C 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.
%C (End)
%D W. H. Gottschalk and G. A. Hedlund, Topological Dynamics. American Mathematical Society, Colloquium Publications, Vol. 36, Providence, RI, 1955, p. 105.
%D M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 23.
%D A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, MD, 1981, p. 6.
%H Robert Israel, <a href="/A010059/b010059.txt">Table of n, a(n) for n = 0..10000</a>
%H J.-P. Allouche and Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps">The Ubiquitous Prouhet-Thue-Morse Sequence</a>, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
%H Scott Balchin and Dan Rust, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Rust/rust3.html">Computations for Symbolic Substitutions</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H Françoise Dejean, <a href="http://dx.doi.org/10.1016/0097-3165(72)90011-8">Sur un Théorème de Thue</a>, J. Combinatorial Theory, vol. 13 A, iss. 1 (1972) 90-99.
%H F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.pdf">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>
%H G. A. Hedlund, <a href="https://www.jstor.org/stable/24525014">Remarks on the work of Axel Thue on sequences</a>, Nordisk Mat. Tid., 15 (1967), 148-150.
%H Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.
%H H. M. Morse, <a href="http://dx.doi.org/10.1090/S0002-9947-1921-1501161-8">Recurrent geodesics on a surface of negative curvature</a>, Trans. Amer. Math. Soc., 22 (1921), 84-100.
%H Stephen Wolfram, <a href="http://www.wolframscience.com/nksonline/page-889c-text?firstview=1">A New Kind Of Science | Online</a>.
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>
%F G.f.: (1/2) * (1/(1-x) + Product_{k>=0} (1 - x^2^k)). - _Ralf Stephan_, Jun 20 2003
%F a(n) = A143579(n) mod 2. - _Gary W. Adamson_, Aug 24 2008
%F a(n) + A010060(n) = 1 for all n.
%F a(n) = A159481(n+1) - A159481(n). - _Reinhard Zumkeller_, Apr 16 2009
%F a(n) + A026147(n-1) = 2n for n >= 1. - _Clark Kimberling_, Oct 06 2014
%F a(n) = A000069(n+1) (mod 2). - _John M. Campbell_, Jun 30 2016
%F a(n) = A059448(A054429(n)) = (A106400(n)+1)/2 = (1+A008836(A005940(1+n)))/2. - _Antti Karttunen_, May 30 2017
%F 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
%F a(n) = (1 + (-1)^A000120(n))/2. - _Lorenzo Sauras Altuzarra_, Mar 10 2024
%e The evolution starting at 1 is:
%e .1
%e .1, 0
%e .1, 0, 0, 1,
%e .1, 0, 0, 1, 0, 1, 1, 0
%e .1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1
%e .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
%e ...........
%p A010059 := n->1-A010060(n);
%p map(t->49-t,convert(StringTools[ThueMorse](1000),bytes)); # _Robert Israel_, Feb 02 2016
%p # second Maple program:
%p a := n -> ifelse(type(add(convert(n, base, 2)), even), 1, 0):
%p seq(a(n), n = 0 .. 104); # _Peter Luschny_, Mar 11 2024
%t Mod[ CoefficientList[Series[(1 + Sqrt[(1 - 3x)/(1 + x)])/(2(1 + x)), {x, 0, 111}], x], 2] (* Stephan Wolfram *)
%t 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 *)
%t Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {1}, 7] (* _Robert G. Wilson v_ Sep 26 2006 *)
%t 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 *)
%t Nest[ Join[ #, Mod[2# + 1, 3]] &, {1}, 7] (* _Robert G. Wilson v_, Jul 27 2014 *)
%t {{1}}~Join~SubstitutionSystem[{0 -> {0, 1}, 1 -> {1, 0}}, {0}, 6] // Flatten (* _Michael De Vlieger_, Aug 15 2016, Version 10.2 *)
%o (Haskell) a010059 = (1 -) . a010060 -- _Reinhard Zumkeller_, Feb 04 2013
%o (PARI) a(n)=!(hammingweight(n)%2); \\ _Charles R Greathouse IV_, Mar 29 2013
%o (R)
%o maxrow <- 8 # by choice
%o b01 <- 0
%o for(m in 0:maxrow) for(k in 0:(2^m-1)){
%o b01[2^(m+1)+ k] <- b01[2^m+k]
%o b01[2^(m+1)+2^m+k] <- 1-b01[2^m+k]
%o }
%o (b01 <- c(1,b01))
%o # _Yosu Yurramendi_, Apr 10 2017
%o (Python)
%o def A010059(n): return n.bit_count()&1^1 # _Chai Wah Wu_, Mar 01 2023
%Y Cf. A001285 (1, 2 version), A010060 (0, 1 version), A106400 (+1, -1 version), A059448 (with reversed subsections).
%Y Cf. also A000069, A026147, A159481.
%Y Cf. A000120, A001969, A143579.
%K nonn,easy
%O 0,1
%A _N. J. A. Sloane_
|
