login
Period-doubling sequence (or period-doubling word): fixed point of the morphism 0 -> 01, 1 -> 00.
40

%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