# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a035263
Showing 1-1 of 1
%I A035263 #240 Aug 06 2024 22:48:36
%S A035263 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 A035263 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 A035263 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 A035263 Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).
%C A035263 First Feigenbaum symbolic (or period-doubling) sequence, corresponding to the accumulation point of the 2^{k} cycles through successive bifurcations.
%C A035263 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 A035263 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 A035263 From _N. J. A. Sloane_, Feb 27 2009: (Start)
%C A035263 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 A035263 If we fill the holes with S we get A141260:
%C A035263 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 A035263 ........1.........0.........1.........1.........0.......1.........1.........0...
%C A035263 - the result is
%C A035263 1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.0.1.... = A141260.
%C A035263 But instead, if we define T recursively by filling the holes in S with the terms of T itself, we get A035263:
%C A035263 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 A035263 ........1.........0.........1.........1.........1.......0.........1.........0...
%C A035263 - the result is
%C A035263 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 A035263 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 A035263 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 A035263 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 A035263 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 A035263 Parity of A007913, A065882 and A065883. - _Philippe Deléham_, Mar 28 2004
%C A035263 The length of n-th run of 1's in this sequence is A080426(n). - _Philippe Deléham_, Apr 19 2004
%C A035263 Also parity of A005043, A005773, A026378, A104455, A117641. - _Philippe Deléham_, Apr 28 2007
%C A035263 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 A035263 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 A035263 a(n) is 1 if the number of trailing zeros in the binary representation of n is even. - _Ralf Stephan_, Aug 22 2013
%C A035263 From _Gary W. Adamson_, Mar 25 2015: (Start)
%C A035263 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 A035263 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 A035263 (End)
%C A035263 The conjecture above was proved by _Jean-Paul Allouche_ on Dec 21 2013.
%C A035263 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 A035263 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 A035263 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 A035263 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 A035263 Manfred R. Schroeder, "Fractals, Chaos, Power Laws", W. H. Freeman, 1991
%D A035263 S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 892, column 2, Note on p. 84, part (a).
%H A035263 Antti Karttunen, Table of n, a(n) for n = 1..65536 (first 10000 terms from T. D. Noe)
%H A035263 Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
%H A035263 J.-P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, A sequence related to that of Thue-Morse, Discrete Math., 139 (1995), 455-461.
%H A035263 J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, 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 A035263 J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, 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 A035263 J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
%H A035263 Joerg Arndt, Matters Computational (The Fxtbook), pp.9-10, pp.734-738
%H A035263 Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
%H A035263 Benoit Cloitre, 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)
%H A035263 F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
%H A035263 B. Derrida, A. Gervois and Y. Pomeau, Iteration of endomorphisms on the real axis and representation of number, Ann. Inst. Henri Poincaré, Section A: Physique Théorique, Vol. XXIX no. 3, 305-356 (1978).
%H A035263 Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
%H A035263 Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.
%H A035263 A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 79. Book's website
%H A035263 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
%H A035263 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H A035263 K. Karamanos, Symbolic Dynamics to a Digital Approach, Int. J. of Bifurcation and Chaos, 11(6), 1683-1694 (2001).
%H A035263 K. Karamanos and G. Nicolis, Symbolic Dynamics and Entropy Analysis of Feigenbaum Limit Sets, Chaos, Solitons and Fractals 10(7), 1135 - 1150 (1999).
%H A035263 D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions
%H A035263 Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
%H A035263 N. Metropolis, M. L. Stein and P. R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44.
%H A035263 Jeffrey Shallit and Anatoly Zavyalov, Transduction of Automatic Sequences and Applications, arXiv:2303.15203 [cs.FL], 2023, see p. 5.
%H A035263 Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
%H A035263 Ralf Stephan, Some divide-and-conquer sequences ...
%H A035263 Ralf Stephan, Table of generating functions
%H A035263 Eric Weisstein's World of Mathematics, Binary carry sequence.
%H A035263 Eric Weisstein's World of Mathematics, Double-free set.
%H A035263 Index entries for characteristic functions
%H A035263 Index entries for sequences related to binary expansion of n
%H A035263 Index entries for sequences that are fixed points of mappings
%F A035263 Absolute values of first differences (A029883) of Thue-Morse sequence (A001285 or A010060). Self-similar under 10->1 and 11->0.
%F A035263 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 A035263 a(n) = Sum_{k>=0} (-1)^k*(floor((n+1)/2^k)-floor(n/2^k)). - _Benoit Cloitre_, Jun 03 2003
%F A035263 Another g.f.: Sum_{k>=0} x^(2^k)/(1+(-1)^k*x^(2^k)). - _Ralf Stephan_, Jun 13 2003
%F A035263 a(2*n) = 1-a(n), a(2*n+1) = 1. - _Ralf Stephan_, Jun 13 2003
%F A035263 a(n) = parity of A033485(n). - _Philippe Deléham_, Aug 13 2003
%F A035263 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 A035263 a(n) = a(n-1) - (-1)^n*a(floor(n/2)). - _Benoit Cloitre_, Dec 02 2003
%F A035263 a(1) = 1 and a(n) = abs(a(n-1) - a(floor(n/2))). - _Benoit Cloitre_, Dec 02 2003
%F A035263 a(n) = 1 - A096268(n+1); A050292 gives partial sums. - _Reinhard Zumkeller_, Aug 16 2006
%F A035263 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 A035263 a(-n) = a(n). a(0)=0. - _Michael Somos_, Sep 04 2006
%F A035263 Dirichlet g.f.: zeta(s)*2^s/(2^s+1). - _Ralf Stephan_, Jun 17 2007
%F A035263 a(n+1) = a(n) XOR a(ceiling(n/2)), a(1) = 1. - _Reinhard Zumkeller_, Jun 11 2009
%F A035263 Let D(x) be the generating function, then D(x) + D(x^2) == x/(1-x). - _Joerg Arndt_, May 11 2010
%F A035263 a(n) = A010060(n) XOR A010060(n+1); a(A079523(n)) = 0; a(A121539(n)) = 1. - _Reinhard Zumkeller_, Mar 01 2012
%F A035263 a((2*n-1)*2^p) = (p+1) mod 2, p >= 0 and n >= 1. - _Johannes W. Meijer_, Feb 07 2013
%F A035263 a(n) = A000035(A001511(n)). - _Omar E. Pol_, Oct 29 2013
%F A035263 a(n) = 2-A056832(n) = (5-A089608(n))/4. - _Antti Karttunen_, Sep 11 2017, after _Benoit Cloitre_
%F A035263 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 A035263 a(n) = A038712(n) mod 3. - _Kevin Ryde_, Jul 11 2019
%F A035263 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 A035263 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 A035263 := n -> 1 - padic[ordp](n, 2) mod 2:
%p A035263 seq(A035263(n), n=1..105); # _Peter Luschny_, Oct 02 2018
%t A035263 a[n_] := a[n] = If[ EvenQ[n], 1 - a[n/2], 1]; Table[ a[n], {n, 1, 105}] (* Or *)
%t A035263 Rest[ CoefficientList[ Series[ Sum[ x^(2^k)/(1 + (-1)^k*x^(2^k)), {k, 0, 20}], {x, 0, 105}], x]]
%t A035263 f[1] := True; f[x_] := Xor[f[x - 1], f[Floor[x/2]]]; a[x_] := Boole[f[x]] (* _Ben Branman_, Oct 04 2010 *)
%t A035263 a[n_] := If[n == 0, 0, 1 - Mod[ IntegerExponent[n, 2], 2]]; (* _Jean-François Alcover_, Jul 19 2013, after _Michael Somos_ *)
%t A035263 Nest[ Flatten[# /. {0 -> {1, 1}, 1 -> {1, 0}}] &, {0}, 7] (* _Robert G. Wilson v_, Jul 23 2014 *)
%t A035263 SubstitutionSystem[{0->{1,1},1->{1,0}},1,{7}][[1]] (* _Harvey P. Dale_, Jun 06 2022 *)
%o A035263 (PARI) {a(n) = if( n==0, 0, 1 - valuation(n, 2)%2)}; /* _Michael Somos_, Sep 04 2006 */
%o A035263 (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 A035263 (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 A035263 (Haskell)
%o A035263 import Data.Bits (xor)
%o A035263 a035263 n = a035263_list !! (n-1)
%o A035263 a035263_list = zipWith xor a010060_list $ tail a010060_list
%o A035263 -- _Reinhard Zumkeller_, Mar 01 2012
%o A035263 (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 A035263 (Python)
%o A035263 def A035263(n): return (n&-n).bit_length()&1 # _Chai Wah Wu_, Jan 09 2023
%Y A035263 Parity of A001511. Anti-parity of A007814.
%Y A035263 Absolute values of first differences of A010060. Apart from signs, same as A029883. Essentially the same as A056832.
%Y A035263 Swapping 0 and 1 gives A096268.
%Y A035263 Cf. A033485, A050292 (partial sums), A089608, A088172, A019300, A039982, A073675, A121701, A141260, A000041, A174065, A220466, A154269 (Mobius transform).
%Y A035263 Limit of A317957(n) for large n.
%Y A035263 Cf. A060572
%K A035263 nonn,easy,nice,mult
%O A035263 1,1
%A A035263 _Karamanos Konstantinos_, _N. J. A. Sloane_
%E A035263 Alternative description added to the name by _Antti Karttunen_, Sep 11 2017
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE