A096268 Period-doubling sequence (or period-doubling word): fixed point of the morphism 0 -> 01, 1 -> 00.
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, 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, 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
Offset: 0
Keywords
Examples
Start: 0 Rules: 0 --> 01 1 --> 00 ------------- 0: (#=1) 0 1: (#=2) 01 2: (#=4) 0100 3: (#=8) 01000101 4: (#=16) 0100010101000100 5: (#=32) 01000101010001000100010101000101 6: (#=64) 0100010101000100010001010100010101000101010001000100010101000100 7: (#=128) 010001010100010001000101010001010100010101000100010001010100010001000101010... [_Joerg Arndt_, Jul 06 2011]
References
- Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
Links
- N. J. A. Sloane, Table of n, a(n) for n = 0..10000 (first 1022 terms from T. D. Noe)
- Jean-Paul Allouche, Michael Baake, Julien Cassaigne, and David Damanik, Palindrome complexity, arXiv:math/0106121 [math.CO], 2001; Theoretical Computer Science, 292 (2003), 9-31.
- Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
- Benoit Cloitre, 200000 steps in the plane using "turn +Pi/3 if a(n)=0 and -2Pi/3 otherwise".
- Cristian Cobeli, Mihai Prunescu, and Alexandru Zaharescu, On non-holonomicity, transcendence and p-adic valuations, arXiv:2412.16517 [math.NT], 2024. See p. 12.
- F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
- G. Jörg Endrullis, Dimitri Hendriks, and Jan Willem Klop, Degrees of streams.
- Robbert Fokkink and Gandhar Joshi, Anti-recurrence sequences, arXiv:2506.13337 [math.NT], 2025. See pp. 2, 18.
- Dimitri Hendriks, Frits G. W. Dannenberg, Jorg Endrullis, Mark Dow and Jan Willem Klop, Arithmetic Self-Similarity of Infinite Sequences, arXiv 1201.3786 [math.CO], 2012.
- Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 79. Book's website
- Shuo Li, Palindromic length sequence of the ruler sequence and of the period-doubling sequence, arXiv:2007.08317 [math.CO], 2020.
- Laszlo Mérai and A. Winterhof, On the Nth linear complexity of automatic sequences, arXiv preprint arXiv:1711.10764 [math.NT], 2017.
- Jeong-Yup Lee, D. Flom and S. I. Ben-Abraham, Multidimensional period doubling structures, Acta Crystallographica Section A: Foundations, (2016). A72, 391-394.
- Aline Parreau, Michel Rigo, Eric Rowland, and Elise Vandomme, A new approach to the 2-regularity of the l-abelian complexity of 2-automatic sequences, arXiv:1405.3532 [cs.FL], 2014-2015.
- Saúl Pilatowsky-Cameo, Soonwon Choi, and Wen Wei Ho, Critically slow Hilbert-space ergodicity in quantum morphic drives, arXiv:2502.06936 [quant-ph], 2025. See pp. 6, 15.
- Narad Rampersad and Manon Stipulanti, The Formal Inverse of the Period-Doubling Sequence, arXiv:1807.11899 [math.CO], 2018.
- Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), Article P1.25.
- Index entries for sequences that are fixed points of mappings.
- Index entries for sequences related to binary expansion of n.
Programs
-
Haskell
a096268 = (subtract 1) . a056832 . (+ 1) -- Reinhard Zumkeller, Jul 29 2014
-
Magma
[Valuation(n+1, 2) mod 2: n in [0..100]]; // Vincenzo Librandi, Jul 20 2016
-
Maple
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 # second Maple program: a:= proc(n) a(n):= `if`(n::even, 0, 1-a((n-1)/2)) end: seq(a(n), n=0..125); # Alois P. Heinz, Mar 20 2019
-
Mathematica
Nest[ Flatten[ # /. {0 -> {1, 0}, 1 -> {0, 0}}] &, {1}, 7] (* Robert G. Wilson v, Mar 05 2005 *) {{0}}~Join~SubstitutionSystem[{0 -> {0, 1}, 1 -> {0, 0}}, {1}, 6] // Flatten (* Michael De Vlieger, Aug 15 2016 *) -
PARI
a(n)=valuation(n+1,2)%2 \\ Ralf Stephan, Nov 11 2013
-
Python
def A096268(n): return (~(n+1)&n).bit_length()&1 # Chai Wah Wu, Jan 09 2023
Formula
Recurrence: a(2*n) = 0, a(4*n+1) = 1, a(4*n+3) = a(n). - Ralf Stephan, Dec 11 2004
The recurrence may be extended backwards, with a(-1) = 1. - S. I. Ben-Abraham, Apr 01 2013
a(n) = 1 - A035263(n-1). - Reinhard Zumkeller, Aug 16 2006
Dirichlet g.f.: zeta(s)/(1+2^s). - Ralf Stephan, Jun 17 2007
Let T(x) be the g.f., then T(x) + T(x^2) = x^2/(1-x^2). - Joerg Arndt, May 11 2010
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
a(n) = A007814(n+1) mod 2. - Robert G. Wilson v, Jan 18 2012
a((2*n+1)*2^p-1) = p mod 2, p >= 0 and n >= 0. - Johannes W. Meijer, Feb 02 2013
a(n) = A056832(n+1) - 1. - Reinhard Zumkeller, Jul 29 2014
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/3. = Amiram Eldar, Sep 18 2022
Extensions
Corrected by Jeremy Gardiner, Dec 12 2004
More terms from Robert G. Wilson v, Feb 26 2005
Comments