A121701 -id:A121701 - cp's OEIS frontend

A003159 Numbers whose binary representation ends in an even number of zeros.

1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 25, 27, 28, 29, 31, 33, 35, 36, 37, 39, 41, 43, 44, 45, 47, 48, 49, 51, 52, 53, 55, 57, 59, 60, 61, 63, 64, 65, 67, 68, 69, 71, 73, 75, 76, 77, 79, 80, 81, 83, 84, 85, 87, 89, 91, 92, 93, 95, 97, 99, 100, 101, 103, 105

Offset: 1

N. J. A. Sloane, Simon Plouffe

Fraenkel (2010) called these the "vile" numbers.
Minimal with respect to property that parity of number of 1's in binary expansion alternates.
Minimal with respect to property that sequence is half its complement. [Corrected by Aviezri S. Fraenkel, Jan 29 2010]
If k appears then 2k does not.
Increasing sequence of positive integers k such that A035263(k)=1 (from paper by Allouche et al.). - Emeric Deutsch, Jan 15 2003
a(n) is an odious number (see A000069) for n odd; a(n) is an evil number (see A001969) for n even. - Philippe Deléham, Mar 16 2004
Indices of odd numbers in A007913, in A001511. - Philippe Deléham, Mar 27 2004
Partial sums of A026465. - Paul Barry, Dec 09 2004
A121701(2*a(n)) = A121701(a(n)); A096268(a(n)-1) = 0. - Reinhard Zumkeller, Aug 16 2006
A different permutation of the same terms may be found in A141290 and the accompanying array. - Gary W. Adamson, Jun 14 2008
a(n) = n-th clockwise Tower of Hanoi move; counterclockwise if not in the sequence. - Gary W. Adamson, Jun 14 2008
Indices of terms of Thue-Morse sequence A010060 which are different from the previous term. - Tanya Khovanova, Jan 06 2009
The sequence has the following fractal property. Remove the odd numbers from the sequence, leaving 4,12,16,20,28,36,44,48,52,... Dividing these terms by 4 we get 1,3,4,5,7,9,11,12,..., which is the original sequence back again. - Benoit Cloitre, Apr 06 2010
From Gary W. Adamson, Mar 21 2010: (Start)
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, ...).
The conjecture states that p(x) = A(x) = A(x^2) when A(x) = polcoeff A174065 = the Euler transform of A035263 = 1/((1-x)*(1-x^3)*(1-x^4)*(1-x^5)*...) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^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 + 2*x^6 + 3*x^8 + 4*x^10 + ....
(End)
The conjecture above was proved by Jean-Paul Allouche on Dec 21 2013. - Gary W. Adamson, Jan 22 2014
If the lower s-Wythoff sequence of s is s, then s=A003159. (See A184117 for the definition of lower and upper s-Wythoff sequences.)  Starting with any nondecreasing sequence s of positive integers, A003159 is the limit when the lower s-Wythoff operation is iterated.  For example, starting with s=(1,4,9,16,...)=(n^2), we obtain lower and upper s-Wythoff sequences
  a=(1,3,4,5,6,8,9,10,11,12,14,...)=A184427;
  b=(2,7,12,21,31,44,58,74,...)=A184428.
  Then putting s=a and repeating the operation gives a'=(1,3,4,5,7,9,11,12,14,...), which has the same first eight terms as A003159. - Clark Kimberling, Jan 14 2011

			1=1, 3=11, 5=101 and 7=111 have no (0 = even) trailing zeros, 4=100 has 2 (= even) trailing zeros in the base-2 representation.
2=10 and 6=110 end in one (=odd number) of trailing zeros in their base-2 representation, therefore are not terms of this sequence. - _M. F. Hasler_, Oct 29 2013

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Lars Blomberg, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Jean-Paul Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, arXiv preprint arXiv:1401.3727 [math.NT], 2014.
Jean-Paul Allouche, Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence, J. de Théorie des Nombres de Bordeaux, 27, no. 2 (2015), 375-388.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See pp. 3, 6.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
Jean-Paul 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.
Jean-Paul 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.
Jean-Paul Allouche, Jeffrey Shallit, and Guentcho Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math. 292 (2005) 1-15.
George E. Andrews and David Newman, Binary Representations and Theta Functions, 2017.
L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fib. Quart., 10 (1972), 499-518, 550.
R. Clerico, P. Fabbri, and F. Ortenzio, Pericolosamente vicino a Collatz, Rudi Mathematici, N. 226 (Nov 2017), p. 14 (in Italian).
Michael Domaratzki, Trajectory-based codes, Acta Informatica, Volume 40, Numbers 6-7 / May, 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
Artūras Dubickas, On the distance from a rational power to the nearest integer, Journal of Number Theory, Volume 117, Issue 1, March 2006, pp. 222-239.
Artūras Dubickas, On a sequence related to that of Thue-Morse and its applications, Discrete Math. 307 (2007), no. 9-10, 1082--1093. MR2292537 (2008b:11086).
Aviezri S. Fraenkel, New games related to old and new sequences, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 4, Paper G6, 2004.
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (2012), no. 1, 42-46.
Aviezri S. Fraenkel, Home Page.
Russell Jay Hendel, A Family of Sequences Generalizing the Thue Morse and Rudin Shapiro Sequences, arXiv:2505.20547 [cs.FL], 2025. See p. 3.
Clark Kimberling, Problem E2850, Amer. Math. Monthly, 87 (1980), 671.
Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160.
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Slides of talk given at Rutgers University, Feb. 2012.
Jan Snellman, Greedy Regular Convolutions, arXiv:2504.02795 [math.NT], 2025.
Eric Sopena, i-Mark: A new subtraction division game, arXiv:1509.04199 [cs.DM], 2015.
David Wakeham and David R. Wood, On multiplicative Sidon sets, INTEGERS, 13 (2013), #A26.
Index entries for 2-automatic sequences.
Index entries for sequences related to binary expansion of n

For the actual binary numbers see A280049.
Indices of even numbers in A007814.
Complement of A036554, also one-half of A036554.
Cf. A001285, A010060, A000041, A174065, A292118.

import Data.List (delete)
a003159 n = a003159_list !! (n-1)
a003159_list = f [1..] where f (x:xs) = x : f (delete  (2*x) xs)
-- Reinhard Zumkeller, Nov 04 2011

filter:= n -> type(padic:-ordp(n,2),even):
select(filter,[$1..1000]); # Robert Israel, Jul 07 2014

f[n_Integer] := Block[{k = n, c = 0}, While[ EvenQ[k], c++; k /= 2]; c]; Select[ Range[105], EvenQ[ f[ # ]] & ]
Select[Range[150],EvenQ[IntegerExponent[#,2]]&] (* Harvey P. Dale, Oct 19 2011 *)

a(n)=if(n<2,n>0,n=a(n-1); until(valuation(n,2)%2==0,n++); n)

is(n)=valuation(n,2)%2==0 \\ Charles R Greathouse IV, Sep 23 2012

from itertools import count, islice
def A003159_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:(n&-n).bit_length()&1,count(max(startvalue,1)))
A003159_list = list(islice(A003159_gen(),30)) # Chai Wah Wu, Jul 11 2022

def A003159(n):
    def f(x):
        c, s = n+x, bin(x)[2:]
        l = len(s)
        for i in range(l&1^1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Jan 29 2025

a(0) = 1; for n >= 0, a(n+1) = a(n) + 1 if (a(n) + 1)/2 is not already in the sequence, = a(n) + 2 otherwise.
Limit_{n->oo} a(n)/n = 3/2. - Benoit Cloitre, Jun 13 2002
More precisely, a(n) = 3*n/2 + O(log n). - Charles R Greathouse IV, Sep 23 2012
a(n) = Sum_{k = 1..n} A026465(k). - Benoit Cloitre, May 31 2003
a(n+1) = (if a(n) mod 4 = 3 then A007814(a(n) + 1) mod 2 else a(n) mod 2) + a(n) + 1; a(1) = 1. - Reinhard Zumkeller, Aug 03 2003
a(A003157(n)) is even. - Philippe Deléham, Feb 22 2004
Sequence consists of numbers of the form 4^i*(2*j + 1), i>=0, j>=0. - Jon Perry, Jun 06 2004
G.f.: (1/(1-x)) * Product_{k >= 1} (1 + x^A001045(k)). - Paul Barry, Dec 09 2004
a(1) = 1, a(2) = 3, and for n >= 2 we get a(n+1) = 4 + a(n) + a(n-1) - a(a(n)-n+1) - a(a(n-1)-n+2). - Benoit Cloitre, Apr 08 2010
If A(x) is the counting function for a(n) <= x, then A(2^n) = (2^(n+1) + (-1)^n)/3. - Vladimir Shevelev, Apr 15 2010
a(n) = A121539(n) + 1. - Reinhard Zumkeller, Mar 01 2012
A003159 = { N | A007814(N) is even }. - M. F. Hasler, Oct 29 2013

Additional comments from Michael Somos
Edited by M. F. Hasler, Oct 29 2013
Incorrect formula removed by Peter Munn, Dec 04 2020

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

Original entry on oeis.org

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, 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, 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

Offset: 1

Karamanos Konstantinos, N. J. A. Sloane

First Feigenbaum symbolic (or period-doubling) sequence, corresponding to the accumulation point of the 2^{k} cycles through successive bifurcations.
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
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]
From N. J. A. Sloane, Feb 27 2009: (Start)
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___...
If we fill the holes with S we get A141260:
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,
........1.........0.........1.........1.........0.......1.........1.........0...
- the result is
1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.0.1.... = A141260.
But instead, if we define T recursively by filling the holes in S with the terms of T itself, we get 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,
........1.........0.........1.........1.........1.......0.........1.........0...
- the result is
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)
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
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
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
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
Parity of A007913, A065882 and A065883. - Philippe Deléham, Mar 28 2004
The length of n-th run of 1's in this sequence is A080426(n). - Philippe Deléham, Apr 19 2004
Also parity of A005043, A005773, A026378, A104455, A117641. - Philippe Deléham, Apr 28 2007
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
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
a(n) is 1 if the number of trailing zeros in the binary representation of n is even. - Ralf Stephan, Aug 22 2013
From Gary W. Adamson, Mar 25 2015: (Start)
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, ...).
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 + ...).
(End)
The conjecture above was proved by Jean-Paul Allouche on Dec 21 2013.
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
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

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)
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)
Manfred R. Schroeder, "Fractals, Chaos, Power Laws", W. H. Freeman, 1991
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 892, column 2, Note on p. 84, part (a).

Antti Karttunen, Table of n, a(n) for n = 1..65536 (first 10000 terms from T. D. Noe)
Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See p. 6.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
Jean-Paul 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.
Jean-Paul Allouche and Michel Mendès 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.
Jean-Paul Allouche and Michel 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]
Jean-Paul 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.
Joerg Arndt, Matters Computational (The Fxtbook), pp.9-10, pp.734-738
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
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)
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
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).
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.
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
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.
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.
Konstantinos Karamanos, Symbolic Dynamics to a Digital Approach, Int. J. of Bifurcation and Chaos, 11(6), 1683-1694 (2001).
Konstantinos Karamanos and Grégoire Nicolis, Symbolic Dynamics and Entropy Analysis of Feigenbaum Limit Sets, Chaos, Solitons and Fractals 10(7), 1135 - 1150 (1999).
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions
Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
Nicholas C. Metropolis, Myron L. Stein and Paul R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44.
Jeffrey Shallit and Anatoly Zavyalov, Transduction of Automatic Sequences and Applications, arXiv:2303.15203 [cs.FL], 2023, see p. 5.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Binary carry sequence.
Eric Weisstein's World of Mathematics, Double-free set.
Index entries for characteristic functions
Index entries for sequences related to binary expansion of n
Index entries for sequences that are fixed points of mappings

Parity of A001511. Anti-parity of A007814.
Absolute values of first differences of A010060. Apart from signs, same as A029883. Essentially the same as A056832.
Swapping 0 and 1 gives A096268.
Cf. A033485, A050292 (partial sums), A089608, A088172, A019300, A039982, A073675, A121701, A141260, A000041, A174065, A220466, A154269 (Mobius transform).
Limit of A317957(n) for large n.
Cf. A060572

import Data.Bits (xor)
a035263 n = a035263_list !! (n-1)
a035263_list = zipWith xor a010060_list $ tail a010060_list
-- Reinhard Zumkeller, Mar 01 2012

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
A035263 := n -> 1 - padic[ordp](n, 2) mod 2:
seq(A035263(n), n=1..105); # Peter Luschny, Oct 02 2018

a[n_] := a[n] = If[ EvenQ[n], 1 - a[n/2], 1]; Table[ a[n], {n, 1, 105}] (* Or *)
Rest[ CoefficientList[ Series[ Sum[ x^(2^k)/(1 + (-1)^k*x^(2^k)), {k, 0, 20}], {x, 0, 105}], x]]
f[1] := True; f[x_] := Xor[f[x - 1], f[Floor[x/2]]]; a[x_] := Boole[f[x]] (* Ben Branman, Oct 04 2010 *)
a[n_] := If[n == 0, 0, 1 - Mod[ IntegerExponent[n, 2], 2]]; (* Jean-François Alcover, Jul 19 2013, after Michael Somos *)
Nest[ Flatten[# /. {0 -> {1, 1}, 1 -> {1, 0}}] &, {0}, 7] (* Robert G. Wilson v, Jul 23 2014 *)
SubstitutionSystem[{0->{1,1},1->{1,0}},1,{7}][[1]] (* Harvey P. Dale, Jun 06 2022 *)

{a(n) = if( n==0, 0, 1 - valuation(n, 2)%2)}; /* Michael Somos, Sep 04 2006 */

{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 */

{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 */

def A035263(n): return (n&-n).bit_length()&1 # Chai Wah Wu, Jan 09 2023

(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

Absolute values of first differences (A029883) of Thue-Morse sequence (A001285 or A010060). Self-similar under 10->1 and 11->0.
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
a(n) = Sum_{k>=0} (-1)^k*(floor((n+1)/2^k)-floor(n/2^k)). - Benoit Cloitre, Jun 03 2003
Another g.f.: Sum_{k>=0} x^(2^k)/(1+(-1)^k*x^(2^k)). - Ralf Stephan, Jun 13 2003
a(2*n) = 1-a(n), a(2*n+1) = 1. - Ralf Stephan, Jun 13 2003
a(n) = parity of A033485(n). - Philippe Deléham, Aug 13 2003
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
a(n) = a(n-1) - (-1)^n*a(floor(n/2)). - Benoit Cloitre, Dec 02 2003
a(1) = 1 and a(n) = abs(a(n-1) - a(floor(n/2))). - Benoit Cloitre, Dec 02 2003
a(n) = 1 - A096268(n+1); A050292 gives partial sums. - Reinhard Zumkeller, Aug 16 2006
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
a(-n) = a(n). a(0)=0. - Michael Somos, Sep 04 2006
Dirichlet g.f.: zeta(s)*2^s/(2^s+1). - Ralf Stephan, Jun 17 2007
a(n+1) = a(n) XOR a(ceiling(n/2)), a(1) = 1. - Reinhard Zumkeller, Jun 11 2009
Let D(x) be the generating function, then D(x) + D(x^2) == x/(1-x). - Joerg Arndt, May 11 2010
a(n) = A010060(n) XOR A010060(n+1); a(A079523(n)) = 0; a(A121539(n)) = 1. - Reinhard Zumkeller, Mar 01 2012
a((2*n-1)*2^p) = (p+1) mod 2, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 07 2013
a(n) = A000035(A001511(n)). - Omar E. Pol, Oct 29 2013
a(n) = 2-A056832(n) = (5-A089608(n))/4. - Antti Karttunen, Sep 11 2017, after Benoit Cloitre
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
a(n) = A038712(n) mod 3. - Kevin Ryde, Jul 11 2019
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

Alternative description added to the name by Antti Karttunen, Sep 11 2017

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 16, 17, 17, 18, 19, 20, 20, 21, 21, 22, 22, 23, 24, 25, 25, 26, 26, 27, 27, 28, 29, 30, 30, 31, 32, 33, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 40, 41, 41, 42, 43, 44, 44, 45, 46, 47, 47, 48, 48, 49, 49, 50, 51, 52, 52, 53, 54

Offset: 0

Eric W. Weisstein

Note that the first equation implies a(0)=0, so there is no need to specify an initial value.
Maximal cardinality of a double-free subset of {1, 2, ..., n}, or in other words, maximal size of a subset S of {1, 2, ..., n} with the property that if x is in S then 2x is not. a(0)=0 by convention.
Least k such that a(k)=n is equal to A003159(n).
To construct the sequence: let [a, b, c, a, a, a, b, c, a, b, c, ...] be the fixed point of the morphism a -> abc, b ->a, c -> a, starting from a(1) = a, then write the indices of a, b, c, that of a being written twice; see A092606. - Philippe Deléham, Apr 13 2004
Number of integers from {1,...,n} for which the subtraction of 1 changes the parity of the number of 1's in their binary expansion. - Vladimir Shevelev, Apr 15 2010
Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. - Vladimir Shevelev, Apr 16 2010
a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. Each number n appears A026465(n+1) times. - Philippe Deléham, Oct 19 2011
Another way of stating the last two comments from Philippe Deléham: the sequence can be obtained by replacing each term of the Thue-Morse sequence A010060 by the run number that term is in. - N. J. A. Sloane, Dec 31 2013

			Examples for n = 1 through 8: {1}, {1}, {1,3}, {1,3,4}, {1,3,4,5}, {1,3,4,5}, {1,3,4,5,7}, {1,3,4,5,7}.
Binary expansion of 5 is 101, so Sum{i>=0} b_i*(-1)^i = 2. Therefore a(5) = 10/3 + 2/3 = 4. - _Vladimir Shevelev_, Apr 15 2010

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.
Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Double-Free Set.

Bisection of A123087.

Cf. A001045, A050291-A050296, A050321, A035263, A121701, A030308, A080277, A120385, A197911.

a050292 n = a050292_list !! (n-1)
a050292_list = scanl (+) 0 a035263_list
-- Reinhard Zumkeller, Jan 21 2013

A050292:=n->add((-1)^k*floor(n/2^k), k=0..n); seq(A050292(n), n=0..100); # Wesley Ivan Hurt, Feb 14 2014

a[n_] := a[n] = If[n < 2, 1, n - a[Floor[n/2]]]; Table[ a[n], {n, 1, 75}]
Join[{0},Accumulate[Nest[Flatten[#/.{0->{1,1},1->{1,0}}]&,{0},7]]] (* Harvey P. Dale, Apr 29 2018 *)

PARI
```
a(n)=if(n<2,1,n-a(floor(n/2)))
```

from sympy.ntheory import digits
def A050292(n): return ((n<<1)+sum((0,1,-1,0)[i] for i in digits(n,4)[1:]))//3 # Chai Wah Wu, Jan 30 2025

Partial sums of A035263. Close to (2/3)*n.
a(n) = A123087(2*n) = n - A123087(n). - Max Alekseyev, Mar 05 2023
From Benoit Cloitre, Nov 24 2002: (Start)
a(1)=1, a(n) = n - a(floor(n/2));
a(n) = (2/3)*n + (1/3)*A065359(n);
more generally, for m>=0, a(2^m*n) - 2^m*a(n) = A001045(m)*A065359(n) where A001045(m) = (2^m - (-1)^m)/3 is the Jacobsthal sequence;
a(A039004(n)) = (2/3)*A039004(n);
a(2*A039004(n)) = 2*a(A039004(n));
a(A003159(n)) = n;
a(A003159(n)-1) = n-1;
a(n) mod 2 = A010060(n) the Thue-Morse sequence;
a(n+1) - a(n) = A035263(n+1);
a(n+2) - a(n) = abs(A029884(n)).
(End)
G.f.: (1/(x-1)) * Sum_{i>=0} (-1)^i*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*floor(n/2^k). - Benoit Cloitre, Jun 03 2003
a(A091785(n)) = 2n; a(A091855(n)) = 2n-1. - Philippe Deléham, Mar 26 2004
a(2^n) = (2^(n+1) + (-1)^n)/3. - Vladimir Shevelev, Apr 15 2010
If n = Sum_{i>=0} b_i*2^i is the binary expansion of n, then a(n) = 2n/3 + (1/3)Sum_{i>=0} b_i*(-1)^i. Thus a(n) = 2n/3 + O(log(n)). - Vladimir Shevelev, Apr 15 2010
Moreover, the equation a(3m)=2m has infinitely many solutions, e.g., a(3*2^k)=2*2^k; on the other hand, a((4^k-1)/3)=(2*(4^k-1))/9+k/3, i.e., limsup |a(n)-2n/3| = infinity. - Vladimir Shevelev, Feb 23 2011
a(n) = Sum_{k>=0} A030308(n,k)*A001045(k+1). - Philippe Deléham, Oct 19 2011
From Peter Bala, Feb 02 2013: (Start)
Product_{n >= 1} (1 + x^((2^n - (-1)^n)/3 )) = (1 + x)^2(1 + x^3)(1 + x^5)(1 + x^11)(1 + x^21)... = 1 + sum {n >= 1} x^a(n) = 1 + 2x + x^2 + x^3 + 2x^4 + 2x^5 + .... Hence this sequence lists the numbers representable as a sum of distinct Jacobsthal numbers A001045 = [1, 1', 3, 5, 11, 21, ...], where we distinguish between the two occurrences of 1 by writing them as 1 and 1'. For example, 9 occurs twice in the present sequence because 9 = 5 + 3 + 1 and 9 = 5 + 3 + 1'. Cf. A197911 and A080277. See also A120385.
(End)

Extended with formula by Christian G. Bower, Sep 15 1999
Corrected and extended by Reinhard Zumkeller, Aug 16 2006
Extended with formula by Philippe Deléham, Oct 19 2011
Entry revised to give a simpler definition by N. J. A. Sloane, Jan 03 2014

cp's OEIS Frontend

A003159 Numbers whose binary representation ends in an even number of zeros.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Scheme

Formula

Extensions

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions