A035263 - OEIS

%I #240 Aug 06 2024 22:48:36

%S 1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,

%T 1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,

%U 1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1

%N Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).

%C First Feigenbaum symbolic (or period-doubling) sequence, corresponding to the accumulation point of the 2^{k} cycles through successive bifurcations.

%C To construct the sequence: start with 1 and concatenate: 1,1, then change the last term (1->0; 0->1) gives: 1,0. Concatenate those 2 terms: 1,0,1,0, change the last term: 1,0,1,1. Concatenate those 4 terms: 1,0,1,1,1,0,1,1 change the last term: 1,0,1,1,1,0,1,0, etc. - _Benoit Cloitre_, Dec 17 2002

%C Let T denote the present sequence. Here is another way to construct T. Start with the sequence S = 1,0,1,_,1,0,1,_,1,0,1,_,1,0,1,_,... and fill in the successive holes with the successive terms of the sequence T (from paper by Allouche et al.). - _Emeric Deutsch_, Jan 08 2003 [Note that if we fill in the holes with the terms of S itself, we get A141260. - _N. J. A. Sloane_, Jan 14 2009]

%C From _N. J. A. Sloane_, Feb 27 2009: (Start)

%C In more detail: define S to be 1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1,0,1___...

%C If we fill the holes with S we get A141260:

%C 1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0,

%C ........1.........0.........1.........1.........0.......1.........1.........0...

%C - the result is

%C 1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.0.1.... = A141260.

%C But instead, if we define T recursively by filling the holes in S with the terms of T itself, we get A035263:

%C 1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0,

%C ........1.........0.........1.........1.........1.......0.........1.........0...

%C - the result is

%C 1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.1.1.0.1.0.1..0..1.1.1..0..1.0.1.. = A035263. (End)

%C Characteristic function of A003159, i.e., A035263(n)=1 if n is in A003159 and A035263(n)=0 otherwise (from paper by Allouche et al.). - _Emeric Deutsch_, Jan 15 2003

%C This is the sequence of R (=1), L (=0) moves in the Towers of Hanoi puzzle: R, L, R, R, R, L, R, L, R, L, R, R, R, ... - _Gary W. Adamson_, Sep 21 2003

%C Manfred Schroeder, p. 279 states, "... the kneading sequences for unimodal maps in the binary notation, 0, 1, 0, 1, 1, 1, 0, 1..., are obtained from the Morse-Thue sequence by taking sums mod 2 of adjacent elements." On p. 278, in the chapter "Self-Similarity in the Logistic Parabola", he writes, "Is there a closer connection between the Morse-Thue sequence and the symbolic dynamics of the superstable orbits? There is indeed. To see this, let us replace R by 1 and C and L by 0." - _Gary W. Adamson_, Sep 21 2003

%C Partial sums modulo 2 of the sequence 1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), a(6), ... . - _Philippe Deléham_, Jan 02 2004

%C Parity of A007913, A065882 and A065883. - _Philippe Deléham_, Mar 28 2004

%C The length of n-th run of 1's in this sequence is A080426(n). - _Philippe Deléham_, Apr 19 2004

%C Also parity of A005043, A005773, A026378, A104455, A117641. - _Philippe Deléham_, Apr 28 2007

%C Equals parity of the Towers of Hanoi, or ruler sequence (A001511), where the Towers of Hanoi sequence (1, 2, 1, 3, 1, 2, 1, 4, ...) denotes the disc moved, labeled (1, 2, 3, ...) starting from the top; and the parity of (1, 2, 1, 3, ...) denotes the direction of the move, CW or CCW. The frequency of CW moves converges to 2/3. - _Gary W. Adamson_, May 11 2007

%C A conjectured identity relating to the partition sequence, A000041: p(x) = A(x) * A(x^2) when A(x) = the Euler transform of A035263 = polcoeff A174065: (1 + x + x^2 + 2x^3 + 3x^4 + 4x^5 + ...). - _Gary W. Adamson_, Mar 21 2010

%C a(n) is 1 if the number of trailing zeros in the binary representation of n is even. - _Ralf Stephan_, Aug 22 2013

%C From _Gary W. Adamson_, Mar 25 2015: (Start)

%C A conjectured identity relating to the partition sequence, A000041 as polcoeff p(x); A003159, and its characteristic function A035263: (1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ...); and A036554 indicating n-th terms with zeros in A035263: (2, 6, 8, 10, 14, 18, 22, ...).

%C The conjecture states that p(x) = A(x) = A(x^2) when A(x) = polcoeffA174065 = the Euler transform of A035263 = 1/(1-x)*(1-x^3)*(1-x^4)*(1-x^5)*... = (1 + x + x^2 + 2x^3 + 3x^4 + 4x^5 + ...) and the aerated variant = the Euler transform of the complement of A035263: 1/(1-x^2)*(1-x^6)*(1-x^8)*... = (1 + x^2 + x^4 + 2x^6 + 3x^8 + 4x^10 + ...).

%C (End)

%C The conjecture above was proved by _Jean-Paul Allouche_ on Dec 21 2013.

%C Regarded as a column vector, this sequence is the product of A047999 (Sierpinski's gasket) regarded as an infinite lower triangular matrix and A036497 (the Fredholm-Rueppel sequence) where the 1's have alternating signs, 1, -1, 0, 1, 0, 0, 0, -1, .... - _Gary W. Adamson_, Jun 02 2021

%C The numbers of 1's through n (A050292) can be determined by starting with the binary (say for 19 = 1 0 0 1 1) and writing: next term is twice current term if 0, otherwise twice plus 1. The result is 1, 2, 4, 9, 19. Take the difference row, = 1, 1, 2, 5, 10; and add the odd-indexed terms from the right: 5, 4, 3, 2, 1 = 10 + 2 + 1 = 13. The algorithm is the basis for determining the disc configurations in the tower of Hanoi game, as shown in the Jul 24 2021 comment of A060572. - _Gary W. Adamson_, Jul 28 2021

%D Karamanos, Kostas. "From symbolic dynamics to a digital approach." International Journal of Bifurcation and Chaos 11.06 (2001): 1683-1694. (Full version. See p. 1685)

%D Karamanos, K. (2000). From symbolic dynamics to a digital approach: chaos and transcendence. In Michel Planat (Ed.), Noise, Oscillators and Algebraic Randomness (Lecture Notes in Physics, pp. 357-371). Springer, Berlin, Heidelberg. (Short version. See p. 359)

%D Manfred R. Schroeder, "Fractals, Chaos, Power Laws", W. H. Freeman, 1991

%D S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 892, column 2, Note on p. 84, part (a).

%H Antti Karttunen, <a href="/A035263/b035263.txt">Table of n, a(n) for n = 1..65536</a> (first 10000 terms from T. D. Noe)

%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2009.02669">Symbolic dynamical scales: modes, orbitals, and transversals</a>, arXiv:2009.02669 [math.DS], 2020.

%H J.-P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, <a href="http://dx.doi.org/10.1016/0012-365X(93)00147-W">A sequence related to that of Thue-Morse</a>, Discrete Math., 139 (1995), 455-461.

%H J.-P. Allouche and M. Mendes France, <a href="https://webusers.imj-prg.fr/~jean-paul.allouche/allmendeshouches.pdf">Automata and Automatic Sequences</a>, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.

%H J.-P. Allouche and M. Mendes France, <a href="/A003842/a003842.pdf">Automata and Automatic Sequences</a>, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]

%H J.-P. Allouche and Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps">The Ubiquitous Prouhet-Thue-Morse Sequence</a>, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.9-10, pp.734-738

%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="/A035263/a035263.png">Fractal walk on the 130000 first terms (step of unit length moving with angle Pi/3 if 0 and -Pi/3 if 1) starting at (0,0)</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 B. Derrida, A. Gervois and Y. Pomeau, <a href="http://www.numdam.org/numdam-bin/item?id=AIHPA_1978__29_3_305_0">Iteration of endomorphisms on the real axis and representation of number</a>, Ann. Inst. Henri Poincaré, Section A: Physique Théorique, Vol. XXIX no. 3, 305-356 (1978).

%H Emeric Deutsch and Bruce E. Sagan, <a href="https://arxiv.org/abs/math/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, arXiv:math/0407326 [math.CO], 2004.

%H Emeric Deutsch and Bruce E. Sagan, <a href="http://dx.doi.org/10.1016/j.jnt.2005.06.005">Congruences for Catalan and Motzkin numbers and related sequences</a>, J. Num. Theory 117 (2006), 191-215.

%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 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.

%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

%H K. Karamanos, <a href="http://dx.doi.org/10.1142/S0218127401002924">Symbolic Dynamics to a Digital Approach</a>, Int. J. of Bifurcation and Chaos, 11(6), 1683-1694 (2001).

%H K. Karamanos and G. Nicolis, <a href="http://dx.doi.org/10.1016/S0960-0779(98)00095-2">Symbolic Dynamics and Entropy Analysis of Feigenbaum Limit Sets</a>, Chaos, Solitons and Fractals 10(7), 1135 - 1150 (1999).

%H D. Kohel, S. Ling and C. Xing, <a href="http://www.maths.usyd.edu.au/u/kohel/doc/perfect.ps">Explicit Sequence Expansions</a>

%H Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, <a href="https://arxiv.org/abs/2207.10171">Pseudoperiodic Words and a Question of Shevelev</a>, arXiv:2207.10171 [math.CO], 2022.

%H N. Metropolis, M. L. Stein and P. R. Stein, <a href="http://dx.doi.org/10.1016/0097-3165(73)90033-2">On finite limit sets for transformations on the unit interval</a>, J. Combin. Theory, A 15 (1973), 25-44.

%H Jeffrey Shallit and Anatoly Zavyalov, <a href="https://arxiv.org/abs/2303.15203">Transduction of Automatic Sequences and Applications</a>, arXiv:2303.15203 [cs.FL], 2023, see p. 5.

%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BinaryCarrySequence.html">Binary carry sequence.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Double-FreeSet.html">Double-free set.</a>

%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>

%F Absolute values of first differences (A029883) of Thue-Morse sequence (A001285 or A010060). Self-similar under 10->1 and 11->0.

%F Series expansion: (1/x) * Sum_{i>=0} (-1)^(i+1)*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003

%F a(n) = Sum_{k>=0} (-1)^k*(floor((n+1)/2^k)-floor(n/2^k)). - _Benoit Cloitre_, Jun 03 2003

%F Another g.f.: Sum_{k>=0} x^(2^k)/(1+(-1)^k*x^(2^k)). - _Ralf Stephan_, Jun 13 2003

%F a(2*n) = 1-a(n), a(2*n+1) = 1. - _Ralf Stephan_, Jun 13 2003

%F a(n) = parity of A033485(n). - _Philippe Deléham_, Aug 13 2003

%F Equals A088172 mod 2, where A088172 = 1, 2, 3, 7, 13, 26, 53, 106, 211, 422, 845, ... (first differences of A019300). - _Gary W. Adamson_, Sep 21 2003

%F a(n) = a(n-1) - (-1)^n*a(floor(n/2)). - _Benoit Cloitre_, Dec 02 2003

%F a(1) = 1 and a(n) = abs(a(n-1) - a(floor(n/2))). - _Benoit Cloitre_, Dec 02 2003

%F a(n) = 1 - A096268(n+1); A050292 gives partial sums. - _Reinhard Zumkeller_, Aug 16 2006

%F Multiplicative with a(2^k) = 1 - (k mod 2), a(p^k) = 1, p > 2. Dirichlet g.f.: Product_{n = 4 or an odd prime} (1/(1-1/n^s)). - _Christian G. Bower_, May 18 2005

%F a(-n) = a(n). a(0)=0. - _Michael Somos_, Sep 04 2006

%F Dirichlet g.f.: zeta(s)*2^s/(2^s+1). - _Ralf Stephan_, Jun 17 2007

%F a(n+1) = a(n) XOR a(ceiling(n/2)), a(1) = 1. - _Reinhard Zumkeller_, Jun 11 2009

%F Let D(x) be the generating function, then D(x) + D(x^2) == x/(1-x). - _Joerg Arndt_, May 11 2010

%F a(n) = A010060(n) XOR A010060(n+1); a(A079523(n)) = 0; a(A121539(n)) = 1. - _Reinhard Zumkeller_, Mar 01 2012

%F a((2*n-1)*2^p) = (p+1) mod 2, p >= 0 and n >= 1. - _Johannes W. Meijer_, Feb 07 2013

%F a(n) = A000035(A001511(n)). - _Omar E. Pol_, Oct 29 2013

%F a(n) = 2-A056832(n) = (5-A089608(n))/4. - _Antti Karttunen_, Sep 11 2017, after _Benoit Cloitre_

%F For n >= 0, a(n+1) = M(2n) mod 2 where M(n) is the Motzkin number A001006 (see Deutsch and Sagan 2006 link). - _David Callan_, Oct 02 2018

%F a(n) = A038712(n) mod 3. - _Kevin Ryde_, Jul 11 2019

%F Given any n in the form (k * 2^m, k odd), extract k and m. Categorize the results into two outcomes of (k, m, even or odd). If (k, m) is (odd, even) substitute 1. If (odd, odd), denote the result 0.  Example: 5 = (5 * 2^0), (odd, even, = 1). (6 = 3 * 2^1), (odd, odd, = 0). - _Gary W. Adamson_, Jun 23 2021

%p nmax:=105: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := (p+1) mod 2 od: od: seq(a(n), n=1..nmax); # _Johannes W. Meijer_, Feb 07 2013

%p A035263 := n -> 1 - padic[ordp](n, 2) mod 2:

%p seq(A035263(n), n=1..105); # _Peter Luschny_, Oct 02 2018

%t a[n_] := a[n] = If[ EvenQ[n], 1 - a[n/2], 1]; Table[ a[n], {n, 1, 105}] (* Or *)

%t Rest[ CoefficientList[ Series[ Sum[ x^(2^k)/(1 + (-1)^k*x^(2^k)), {k, 0, 20}], {x, 0, 105}], x]]

%t f[1] := True; f[x_] := Xor[f[x - 1], f[Floor[x/2]]]; a[x_] := Boole[f[x]] (* _Ben Branman_, Oct 04 2010 *)

%t a[n_] := If[n == 0, 0, 1 - Mod[ IntegerExponent[n, 2], 2]]; (* _Jean-François Alcover_, Jul 19 2013, after _Michael Somos_ *)

%t Nest[ Flatten[# /. {0 -> {1, 1}, 1 -> {1, 0}}] &, {0}, 7] (* _Robert G. Wilson v_, Jul 23 2014 *)

%t SubstitutionSystem[{0->{1,1},1->{1,0}},1,{7}][[1]] (* _Harvey P. Dale_, Jun 06 2022 *)

%o (PARI) {a(n) = if( n==0, 0, 1 - valuation(n, 2)%2)}; /* _Michael Somos_, Sep 04 2006 */

%o (PARI) {a(n) = if( n==0, 0, n = abs(n); subst( Pol(binary(n)) - Pol(binary(n-1)), x, 1)%2)}; /* _Michael Somos_, Sep 04 2006 */

%o (PARI) {a(n) = if( n==0, 0, n = abs(n); direuler(p=2, n, 1 / (1 - X^((p<3) + 1)))[n])}; /* _Michael Somos_, Sep 04 2006 */

%o (Haskell)

%o import Data.Bits (xor)

%o a035263 n = a035263_list !! (n-1)

%o a035263_list = zipWith xor a010060_list $ tail a010060_list

%o -- _Reinhard Zumkeller_, Mar 01 2012

%o (Scheme) (define (A035263 n) (let loop ((n n) (i 1)) (cond ((odd? n) (modulo i 2)) (else (loop (/ n 2) (+ 1 i)))))) ;; (Use mod instead of modulo in R6RS) _Antti Karttunen_, Sep 11 2017

%o (Python)

%o def A035263(n): return (n&-n).bit_length()&1 # _Chai Wah Wu_, Jan 09 2023

%Y Parity of A001511. Anti-parity of A007814.

%Y Absolute values of first differences of A010060. Apart from signs, same as A029883. Essentially the same as A056832.

%Y Swapping 0 and 1 gives A096268.

%Y Cf. A033485, A050292 (partial sums), A089608, A088172, A019300, A039982, A073675, A121701, A141260, A000041, A174065, A220466, A154269 (Mobius transform).

%Y Limit of A317957(n) for large n.

%Y Cf. A060572

%K nonn,easy,nice,mult

%O 1,1

%A _Karamanos Konstantinos_, _N. J. A. Sloane_

%E Alternative description added to the name by _Antti Karttunen_, Sep 11 2017