A071858 -id:A071858 - cp's OEIS frontend

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

N. J. A. Sloane, Jun 22 2004

nonn

Take highest power of 2 dividing n (A007814(n+1)), read modulo 2.
For the scale-invariance properties see Hendriks et al., 2012.
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
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
1 iff the number of trailing zeros in the binary representation of n+1 is odd. - Ralf Stephan, Nov 11 2013
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

			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]

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

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.

Not the same as A073059!
Swapping 0 and 1 gives A035263.
Cf. A096269, A096270, A071858, A220466, A036577.
Cf. A056832, A123087 (partial sums).
With offset 1, classification indicator for A003159/A036554.
Also with offset 1: A007814 mod 2 (cf. A096271 for mod 3), A048675 mod 2 (cf. A332813 for mod 3), A059975 mod 2.

a096268 = (subtract 1) . a056832 . (+ 1)
-- Reinhard Zumkeller, Jul 29 2014

[Valuation(n+1, 2) mod 2: n in [0..100]]; // Vincenzo Librandi, Jul 20 2016

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

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 *)

a(n)=valuation(n+1,2)%2 \\ Ralf Stephan, Nov 11 2013

def A096268(n): return (~(n+1)&n).bit_length()&1 # Chai Wah Wu, Jan 09 2023

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

Corrected by Jeremy Gardiner, Dec 12 2004

More terms from Robert G. Wilson v, Feb 26 2005

A096271 Ternary sequence that is a fixed point of the morphism 0 -> 01, 1 -> 02, 2 -> 00.

Original entry on oeis.org

0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 0, 0

Offset: 0

N. J. A. Sloane, Jun 23 2004

Antti Karttunen, Table of n, a(n) for n = 0..65537
Index entries for sequences that are fixed points of mappings.

Cf. A007814, A071858.

Nest[ Function[ l, {Flatten[(l /. {0 -> {0, 1}, 1 -> {0, 2}, 2 -> {0, 0}})]}], {0}, 7] (* Robert G. Wilson v, Feb 26 2005 *)

map(d)=if(d==2,[0,0],if(d==1,[0,2],[0,1]))
{m=53;v=[];w=[0];while(v!=w,v=w;w=[];for(n=1,min(m,length(v)),w=concat(w,map(v[n]))));for(n=1,2*m,print1(v[n],","))} \\ Klaus Brockhaus, Jun 23 2004

A096271(n) = if(!(n%2),0,(1+A096271((n-1)/2))%3); \\ Antti Karttunen, Nov 01 2018

def A096271(n): return (~(n+1) & n).bit_length()%3 # Chai Wah Wu, Jan 09 2023

Recurrence: a(2n) = 0, a(2n+1) = (a(n)+1) mod 3. - Ralf Stephan, Dec 11 2004
a(n) = A007814(n+1) mod 3. - Gabriele Fici, Mar 28 2019
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 4/7. - Amiram Eldar, Jan 11 2023

More terms from Klaus Brockhaus, Jun 23 2004

A179868 (Number of 1's in the binary expansion of n) mod 4.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 0, 1, 2, 2, 3, 2, 3, 3, 0, 2, 3, 3, 0, 3, 0, 0, 1, 1, 2, 2, 3, 2, 3, 3, 0, 2, 3, 3, 0, 3, 0, 0, 1, 2, 3, 3, 0, 3, 0, 0, 1, 3, 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 3, 2, 3, 3, 0, 2, 3, 3, 0, 3, 0, 0, 1, 2, 3, 3, 0, 3, 0, 0, 1, 3, 0, 0, 1, 0, 1, 1, 2, 2, 3, 3, 0, 3

Offset: 0

N. J. A. Sloane, Jan 11 2011

This is the generalized Thue-Morse sequence t_4 (Allouche and Shallit, p. 335).

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

Cf. A000120, A010873, A010060 (mod 2), A071858 (mod 3).

Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {1, 2}, 2 -> {2, 3}, 3 -> {3, 0}}] &, {0}, 7] (* Robert G. Wilson v, May 17 2014 *)
Table[Mod[DigitCount[n,2,1],4],{n,0,110}] (* Harvey P. Dale, Jul 24 2016 *)

a(n)=hammingweight(n)%4 \\ Charles R Greathouse IV, May 09 2016

a(n) = A010873(A000120(n)).

A245555 Trajectory of 1 under the morphism 1 -> 12, 2 -> 23, 3 -> 31.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 3, 1, 2, 3, 3, 1, 3, 1, 1, 2, 2, 3, 3, 1, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 2, 3, 2, 3, 3, 1, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 2, 3, 3, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 1, 2, 3, 3, 1, 3, 1, 1, 2, 3, 1, 1, 2, 1, 2, 2, 3, 3, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3

Offset: 1

N. J. A. Sloane, Aug 03 2014

nonn

The morphism 1->12, 2->21 gives the {1,2} version of the Thue-Morse sequence A001285, cf. A010060.

The morphism 0->01, 1->12, 2->20 gives the generalized Thue-Morse sequence A071858.

Cf. A001285, A010060, A092782, A105083, A245553, A245554.

Essentially the same as A071858.

Nest[ Function[ l, {Flatten[(l /. {1 -> {1, 2}, 2 -> {2, 3}, 3 -> {3, 1}})] }], {1}, 9]

{a(n) = my(v = [1]); if( n<1, 0, while( #vMichael Somos, Aug 05 2014 */

a(n) = A071858(n+1) + 1. - Michel Dekking, Sep 29 2020

A234538 (Number of positive digits of n written in base 3) modulo 3.

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 2, 0, 0, 2, 0, 0, 1, 2, 2, 2, 0, 0, 2, 0, 0, 1, 2, 2, 2, 0, 0, 2, 0, 0, 2, 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 2, 0, 0, 2, 0, 0, 2, 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 2, 0, 0, 2, 0, 0, 2, 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 0, 0, 1, 1

Offset: 0

Vladimir Shevelev, Jan 13 2014

Since A000120 is the number of positive digits of n written in binary, this sequence is a formal ternary analog of the Thue-Morse sequence A010060. However, one cannot name it a "ternary version of A010060" like the known versions A053838, A071858, A036577-A036586, since it is not "cubefree"; i.e., it contains the same 3 consecutive terms, and there is not a known morphism for which it is a fixed point.

Peter J. C. Moses, Table of n, a(n) for n = 0..999

Cf. A000120, A010060, A036577-A036586, A053838, A071858, A160384.

a[n_] := Mod[Plus @@ DigitCount[n, 3, {1, 2}], 3]; Array[a, 100, 0] (* Amiram Eldar, Jul 24 2023 *)

a(n)=my(d=digits(n, 3)); sum(i=1, #d, !d[i])%3 \\ Charles R Greathouse IV, Jan 13 2014

A160384(n) == a(n) (mod 3).

A179854 Number of 0's (mod 3) in the binary expansion of n.

Original entry on oeis.org

0, 1, 0, 2, 1, 1, 0, 0, 2, 2, 1, 2, 1, 1, 0, 1, 0, 0, 2, 0, 2, 2, 1, 0, 2, 2, 1, 2, 1, 1, 0, 2, 1, 1, 0, 1, 0, 0, 2, 1, 0, 0, 2, 0, 2, 2, 1, 1, 0, 0, 2, 0, 2, 2, 1, 0, 2, 2, 1, 2, 1, 1, 0, 0, 2, 2, 1, 2, 1, 1, 0, 2, 1, 1, 0, 1, 0, 0, 2, 2, 1, 1, 0, 1, 0, 0, 2, 1, 0, 0, 2, 0, 2, 2, 1, 2, 1, 1, 0, 1, 0, 0, 2, 1, 0, 0, 2, 0, 2, 2, 1, 1, 0, 0, 2, 0, 2, 2, 1, 0

Offset: 1

N. J. A. Sloane, Jan 11 2011

nonn

A ternary analog of A059448.
Offset is 1 to avoid the ambiguity at n=0.
Inspired by Chapter 1 of Allouche and Shallit.
From Michel Dekking, Sep 30 2020: (Start)
Let tau be the "twisted" 3-symbol length 2 Thue-Morse morphism given by
      tau(0) = 10, tau(1) = 21, tau (2) = 02.
The name of tau is in analogy with the comments from A297531. The "ordinary" 3-symbol length 2 Thue-Morse morphism is the morphism mu given by
      mu(0) = 01, mu(1) = 12, mu(2) = 20.
The unique fixed point of mu is the sequence A071858 = 01121220...
We have mu^3 = tau^3.
The sequence a = (a(n)) satisfies
      a = 0 tau(a).
This follows directly from the recursion formulas
      a(2n) = a(n) + 1 mod 3, a(2n+1) = a(n).
(End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

Cf. A059448. Related to A071858.

s1:=[];
for n from 0 to 200 do
t1:=convert(n,base,2); t2:=subs(1=NULL,t1); s1:=[op(s1),nops(t2) mod 3]; od:
s1;

a(2n) = a(n) + 1 mod 3, a(2n+1) = a(n). - Michel Dekking, Sep 30 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A096271 Ternary sequence that is a fixed point of the morphism 0 -> 01, 1 -> 02, 2 -> 00.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A179868 (Number of 1's in the binary expansion of n) mod 4.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

PARI

Formula

A245555 Trajectory of 1 under the morphism 1 -> 12, 2 -> 23, 3 -> 31.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A234538 (Number of positive digits of n written in base 3) modulo 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A179854 Number of 0's (mod 3) in the binary expansion of n.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Maple

Formula