|
%I #171 Feb 08 2024 07:13:47
%S 0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,
%T 0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,
%U 0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0
%N Period-doubling sequence (or period-doubling word): fixed point of the morphism 0 -> 01, 1 -> 00.
%C Take highest power of 2 dividing n (A007814(n+1)), read modulo 2.
%C For the scale-invariance properties see Hendriks et al., 2012.
%C This is the sequence that results from the ternary Thue-Morse sequence (A036577) if all twos in that sequence are replaced by zeros. - _Nathan Fox_, Mar 12 2013
%C This sequence can be used to draw the Von Koch snowflake with a suitable walk in the plane. Start from the origin then the n-th step is "turn +Pi/3 if a(n)=0 and turn -2*Pi/3 if a(n)=1" (see link for a plot of the first 200000 steps). - _Benoit Cloitre_, Nov 10 2013
%C 1 iff the number of trailing zeros in the binary representation of n+1 is odd. - _Ralf Stephan_, Nov 11 2013
%C Equivalently, with offset 1, the characteristic function of A036554 and an indicator for the A003159/A036554 classification of positive integers. - _Peter Munn_, Jun 02 2020
%D Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%H N. J. A. Sloane, <a href="/A096268/b096268.txt">Table of n, a(n) for n = 0..10000</a> (first 1022 terms from T. D. Noe)
%H J.-P. Allouche, M. Baake, J. Cassaigns, and D. Damanik, <a href="http://arxiv.org/abs/math/0106121">Palindrome complexity</a>, arXiv:math/0106121 [math.CO], 2001; <a href="http://dx.doi.org/10.1016/S0304-3975(01)00212-2">Theoretical Computer Science</a>, 292 (2003), 9-31.
%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 Benoit Cloitre, <a href="/A096268/a096268.png">200000 steps in the plane using "turn +Pi/3 if a(n)=0 and -2Pi/3 otherwise"</a>.
%H F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H G. J. Endrullis, D. Hendriks and J. W. Klop, <a href="http://joerg.endrullis.de/assets/papers/streams-degrees-2011.pdf">Degrees of streams</a>.
%H Dimitri Hendriks, Frits G. W. Dannenberg, Jorg Endrullis, Mark Dow and Jan Willem Klop, <a href="http://arxiv.org/abs/1201.3786">Arithmetic Self-Similarity of Infinite Sequences</a>, arXiv 1201.3786 [math.CO], 2012.
%H A. M. Hinz, S. Klavžar, U. Milutinović and C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See page 79. <a href="http://tohbook.info">Book's website</a>
%H Shuo Li, <a href="https://arxiv.org/abs/2007.08317">Palindromic length sequence of the ruler sequence and of the period-doubling sequence</a>, arXiv:2007.08317 [math.CO], 2020.
%H Laszlo Mérai and A. Winterhof, <a href="https://arxiv.org/abs/1711.10764">On the Nth linear complexity of automatic sequences</a>, arXiv preprint arXiv:1711.10764 [math.NT], 2017.
%H Jeong-Yup Lee, D. Flom and S. I. Ben-Abraham, <a href="https://doi.org/10.1107/S2053273316004897">Multidimensional period doubling structures</a>, Acta Crystallographica Section A: Foundations, (2016). A72, 391-394.
%H A. Parreau, M. Rigo, E. Rowland and E. Vandomme, <a href="http://arxiv.org/abs/1405.3532">A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences</a>, arXiv:1405.3532 [cs.FL], 2014-2015.
%H Narad Rampersad and Manon Stipulanti, <a href="https://arxiv.org/abs/1807.11899">The Formal Inverse of the Period-Doubling Sequence</a>, arXiv:1807.11899 [math.CO], 2018.
%H Luke Schaeffer and Jeffrey Shallit, <a href="https://doi.org/10.37236/5752">Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences</a>, Electronic Journal of Combinatorics 23(1) (2016), Article P1.25.
%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>.
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.
%F Recurrence: a(2*n) = 0, a(4*n+1) = 1, a(4*n+3) = a(n). - _Ralf Stephan_, Dec 11 2004
%F The recurrence may be extended backwards, with a(-1) = 1. - S. I. Ben-Abraham, Apr 01 2013
%F a(n) = 1 - A035263(n-1). - _Reinhard Zumkeller_, Aug 16 2006
%F Dirichlet g.f.: zeta(s)/(1+2^s). - _Ralf Stephan_, Jun 17 2007
%F Let T(x) be the g.f., then T(x) + T(x^2) = x^2/(1-x^2). - _Joerg Arndt_, May 11 2010
%F Let 2^k||n+1. Then a(n)=1 if k is odd, a(n)=0 if k is even. - _Vladimir Shevelev_, Aug 25 2010
%F a(n) = A007814(n+1) mod 2. - _Robert G. Wilson v_, Jan 18 2012
%F a((2*n+1)*2^p-1) = p mod 2, p >= 0 and n >= 0. - _Johannes W. Meijer_, Feb 02 2013
%F a(n) = A056832(n+1) - 1. - _Reinhard Zumkeller_, Jul 29 2014
%F Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/3. = _Amiram Eldar_, Sep 18 2022
%e Start: 0
%e Rules:
%e 0 --> 01
%e 1 --> 00
%e -------------
%e 0: (#=1)
%e 0
%e 1: (#=2)
%e 01
%e 2: (#=4)
%e 0100
%e 3: (#=8)
%e 01000101
%e 4: (#=16)
%e 0100010101000100
%e 5: (#=32)
%e 01000101010001000100010101000101
%e 6: (#=64)
%e 0100010101000100010001010100010101000101010001000100010101000100
%e 7: (#=128)
%e 010001010100010001000101010001010100010101000100010001010100010001000101010...
%e [_Joerg Arndt_, Jul 06 2011]
%p nmax:=104: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 0 to ceil(nmax/(p+2))+1 do a((2*n+1)*2^p-1) := p mod 2 od: od: seq(a(n), n=0..nmax); # _Johannes W. Meijer_, Feb 02 2013
%p # second Maple program:
%p a:= proc(n) a(n):= `if`(n::even, 0, 1-a((n-1)/2)) end:
%p seq(a(n), n=0..125); # _Alois P. Heinz_, Mar 20 2019
%t Nest[ Flatten[ # /. {0 -> {1, 0}, 1 -> {0, 0}}] &, {1}, 7] (* _Robert G. Wilson v_, Mar 05 2005 *)
%t {{0}}~Join~SubstitutionSystem[{0 -> {0, 1}, 1 -> {0, 0}}, {1}, 6] // Flatten (* _Michael De Vlieger_, Aug 15 2016, Version 10.2 *)
%o (PARI) a(n)=valuation(n+1,2)%2 \\ _Ralf Stephan_, Nov 11 2013
%o (Haskell)
%o a096268 = (subtract 1) . a056832 . (+ 1)
%o -- _Reinhard Zumkeller_, Jul 29 2014
%o (Magma) [Valuation(n+1, 2) mod 2: n in [0..100]]; // _Vincenzo Librandi_, Jul 20 2016
%o (Python)
%o def A096268(n): return (~(n+1)&n).bit_length()&1 # _Chai Wah Wu_, Jan 09 2023
%Y Not the same as A073059!
%Y Swapping 0 and 1 gives A035263.
%Y Cf. A096269, A096270, A071858, A220466, A036577.
%Y Cf. A056832, A123087 (partial sums).
%Y With offset 1, classification indicator for A003159/A036554.
%Y Also with offset 1: A007814 mod 2 (cf. A096271 for mod 3), A048675 mod 2 (cf. A332813 for mod 3), A059975 mod 2.
%K nonn
%O 0,1
%A _N. J. A. Sloane_, Jun 22 2004
%E Corrected by _Jeremy Gardiner_, Dec 12 2004
%E More terms from _Robert G. Wilson v_, Feb 26 2005
|
