cp's OEIS Frontend

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

%I A096268 #183 Jun 23 2025 10:54:43
%S A096268 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 A096268 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 A096268 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 A096268 Period-doubling sequence (or period-doubling word): fixed point of the morphism 0 -> 01, 1 -> 00.
%C A096268 Take highest power of 2 dividing n (A007814(n+1)), read modulo 2.
%C A096268 For the scale-invariance properties see Hendriks et al., 2012.
%C A096268 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 A096268 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 A096268 1 iff the number of trailing zeros in the binary representation of n+1 is odd. - _Ralf Stephan_, Nov 11 2013
%C A096268 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 A096268 Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
%H A096268 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 A096268 Jean-Paul Allouche, Michael Baake, Julien Cassaigne, and David 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 A096268 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 A096268 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 A096268 Cristian Cobeli, Mihai Prunescu, and Alexandru Zaharescu, <a href="https://arxiv.org/abs/2412.16517">On non-holonomicity, transcendence and p-adic valuations</a>, arXiv:2412.16517 [math.NT], 2024. See p. 12.
%H A096268 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 A096268 G. Jörg Endrullis, Dimitri Hendriks, and Jan Willem Klop, <a href="http://joerg.endrullis.de/assets/papers/streams-degrees-2011.pdf">Degrees of streams</a>.
%H A096268 Robbert Fokkink and Gandhar Joshi, <a href="https://arxiv.org/abs/2506.13337">Anti-recurrence sequences</a>, arXiv:2506.13337 [math.NT], 2025. See pp. 2, 18.
%H A096268 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 A096268 Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril 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 A096268 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 A096268 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 A096268 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 A096268 Aline Parreau, Michel Rigo, Eric Rowland, and Elise 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 A096268 Saúl Pilatowsky-Cameo, Soonwon Choi, and Wen Wei Ho, <a href="https://arxiv.org/abs/2502.06936">Critically slow Hilbert-space ergodicity in quantum morphic drives</a>, arXiv:2502.06936 [quant-ph], 2025. See pp. 6, 15.
%H A096268 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 A096268 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 A096268 <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>.
%H A096268 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.
%F A096268 Recurrence: a(2*n) = 0, a(4*n+1) = 1, a(4*n+3) = a(n). - _Ralf Stephan_, Dec 11 2004
%F A096268 The recurrence may be extended backwards, with a(-1) = 1. - S. I. Ben-Abraham, Apr 01 2013
%F A096268 a(n) = 1 - A035263(n-1). - _Reinhard Zumkeller_, Aug 16 2006
%F A096268 Dirichlet g.f.: zeta(s)/(1+2^s). - _Ralf Stephan_, Jun 17 2007
%F A096268 Let T(x) be the g.f., then T(x) + T(x^2) = x^2/(1-x^2). - _Joerg Arndt_, May 11 2010
%F A096268 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 A096268 a(n) = A007814(n+1) mod 2. - _Robert G. Wilson v_, Jan 18 2012
%F A096268 a((2*n+1)*2^p-1) = p mod 2, p >= 0 and n >= 0. - _Johannes W. Meijer_, Feb 02 2013
%F A096268 a(n) = A056832(n+1) - 1. - _Reinhard Zumkeller_, Jul 29 2014
%F A096268 Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/3. = _Amiram Eldar_, Sep 18 2022
%e A096268 Start: 0
%e A096268 Rules:
%e A096268   0 --> 01
%e A096268   1 --> 00
%e A096268 -------------
%e A096268 0:   (#=1)
%e A096268   0
%e A096268 1:   (#=2)
%e A096268   01
%e A096268 2:   (#=4)
%e A096268   0100
%e A096268 3:   (#=8)
%e A096268   01000101
%e A096268 4:   (#=16)
%e A096268   0100010101000100
%e A096268 5:   (#=32)
%e A096268   01000101010001000100010101000101
%e A096268 6:   (#=64)
%e A096268   0100010101000100010001010100010101000101010001000100010101000100
%e A096268 7:   (#=128)
%e A096268   010001010100010001000101010001010100010101000100010001010100010001000101010...
%e A096268 [_Joerg Arndt_, Jul 06 2011]
%p A096268 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 A096268 # second Maple program:
%p A096268 a:= proc(n) a(n):= `if`(n::even, 0, 1-a((n-1)/2)) end:
%p A096268 seq(a(n), n=0..125);  # _Alois P. Heinz_, Mar 20 2019
%t A096268 Nest[ Flatten[ # /. {0 -> {1, 0}, 1 -> {0, 0}}] &, {1}, 7] (* _Robert G. Wilson v_, Mar 05 2005 *)
%t A096268 {{0}}~Join~SubstitutionSystem[{0 -> {0, 1}, 1 -> {0, 0}}, {1}, 6] // Flatten (* _Michael De Vlieger_, Aug 15 2016 *)
%o A096268 (PARI) a(n)=valuation(n+1,2)%2 \\ _Ralf Stephan_, Nov 11 2013
%o A096268 (Haskell)
%o A096268 a096268 = (subtract 1) . a056832 . (+ 1)
%o A096268 -- _Reinhard Zumkeller_, Jul 29 2014
%o A096268 (Magma) [Valuation(n+1, 2) mod 2: n in [0..100]]; // _Vincenzo Librandi_, Jul 20 2016
%o A096268 (Python)
%o A096268 def A096268(n): return (~(n+1)&n).bit_length()&1 # _Chai Wah Wu_, Jan 09 2023
%Y A096268 Not the same as A073059!
%Y A096268 Swapping 0 and 1 gives A035263.
%Y A096268 Cf. A096269, A096270, A071858, A220466, A036577.
%Y A096268 Cf. A056832, A123087 (partial sums).
%Y A096268 With offset 1, classification indicator for A003159/A036554.
%Y A096268 Also with offset 1: A007814 mod 2 (cf. A096271 for mod 3), A048675 mod 2 (cf. A332813 for mod 3), A059975 mod 2.
%K A096268 nonn
%O A096268 0,1
%A A096268 _N. J. A. Sloane_, Jun 22 2004
%E A096268 Corrected by _Jeremy Gardiner_, Dec 12 2004
%E A096268 More terms from _Robert G. Wilson v_, Feb 26 2005