A036585 -id:A036585 - cp's OEIS frontend

A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.

0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60, 63, 65, 66, 68, 71, 72, 75, 77, 78, 80, 83, 85, 86, 89, 90, 92, 95, 96, 99, 101, 102, 105, 106, 108, 111, 113, 114, 116, 119, 120, 123, 125, 126, 129

Offset: 1

N. J. A. Sloane

This sequence and A000069 give the unique solution to the problem of splitting the nonnegative integers into two classes in such a way that sums of pairs of distinct elements from either class occur with the same multiplicities [Lambek and Moser]. Cf. A000028, A000379.
In French: les nombres païens.
Theorem: First differences give A036585. (Observed by Franklin T. Adams-Watters.)
Proof from Max Alekseyev, Aug 30 2006 (edited by N. J. A. Sloane, Jan 05 2021): (Start)
Observe that if the last bit of a(n) is deleted, we get the nonnegative numbers 0, 1, 2, 3, ... in order.
The last bit in a(n+1) is 1 iff the number of bits in n is odd, that is, iff A010060(n+1) is 1.
So, taking into account the different offsets here and in A010060, we have a(n) = 2*(n-1) + A010060(n-1).
Therefore the first differences of the present sequence equal 2 + first differences of A010060, which equals A036585.  QED (End)
Integers k such that A010060(k-1)=0. - Benoit Cloitre, Nov 15 2003
Indices of zeros in the Thue-Morse sequence A010060 shifted by 1. - Tanya Khovanova, Feb 13 2009
Conjecture, checked up to 10^6: a(n) is also the sequence of numbers k representable as k = ror(x) XOR rol(x) (for some integer x) where ror(x)=A038572(x) is x rotated one binary place to the right, rol(x)=A006257(x) is x rotated one binary place to the left, and XOR is the binary exclusive-or operator. - Alex Ratushnyak, May 14 2016
From Charlie Neder, Oct 07 2018: (Start)
Conjecture is true: ror(x) and rol(x) have an even number of 1 bits in total (= 2 * A000120(x)), and XOR preserves the parity of this total, so the resulting number must have an even number of 1 bits. An x can be constructed corresponding to a(n) like so:
If the number of bits in a(n) is even, add a leading 0 so a(n) is 2k+1 bits long.
Do an inverse shuffle on a(n), then "divide" by 11, rotate the result k bits to the right, and shuffle to get x. (End)
Numbers of the form m XOR (2*m) for some m >= 0. - Rémy Sigrist, Feb 07 2021
The terms "evil numbers" and "odious numbers" were coined by Richard K. Guy, c. 1976 (Haque and Shallit, 2016) and appeared in the book by Berlekamp et al. (Vol. 1, 1st ed., 1982). - Amiram Eldar, Jun 08 2021

Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, 2nd ed., A K Peters, 2001, chapter 14, p. 110.
Hugh L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
Donald J. Newman, A Problem Seminar, Springer; see Problem #89.
Vladimir S. Shevelev, On some identities connected with the partition of the positive integers with respect to the Morse sequence, Izv. Vuzov of the North-Caucasus region, Nature sciences 4 (1997), 21-23 (Russian).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche and Henri Cohen, Dirichlet series and curious infinite products, Bull. London Math. Soc., Vol. 17 (1985), pp. 531-538.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197; DOI.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, Aequationes mathematicae, Vol. 90 (2016), pp. 341-353; alternative link.
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 19.
Chris Bernhardt, Evil twins alternate with odious twins, Math. Mag., Vol. 82, No. 1 (2009), pp. 57-62; alternative link.
Joshua N. Cooper, Dennis Eichhorn and Kevin O'Bryant, Reciprocals of binary power series, International Journal of Number Theory, Vol. 2, No. 4 (2006), pp. 499-522; arXiv preprint, arXiv:math/0506496 [math.NT], 2005.
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math., Vol. 312, No. 1 (2012), pp. 42-46.
E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presque premiers, (French) [Sums of digits and almost primes] Math. Ann., Vol. 305, No. 3 (1996), pp. 571-599. MR1397437 (97k:11029)
Sajed Haque, Chapter 3.2 of Discriminators of Integer Sequences, thesis, University of Waterloo, Ontario, Canada, 2017. See p. 38.
Sajed Haque and Jeffrey Shallit, Discriminators and k-Regular Sequences Integers, Vol. 16 (2016), Article A76; arXiv preprint, arXiv:1605.00092 [cs.DM], 2016.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
J. Lambek and L. Moser, On some two way classifications of integers, Canad. Math. Bull., Vol. 2, No. 2 (1959), pp. 85-89.
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., Vol. 3, No. 4 (1974), pp. 255-261.
Jeffrey O. Shallit, On infinite products associated with sums of digits, J. Number Theory, Vol. 21, No. 2 (1985), pp. 128-134.
Jeffrey Shallit, Frobenius Numbers and Automatic Sequences, arXiv:2103.10904 [math.NT], 2021.
Jeffrey Shallit, Additive Number Theory via Automata and Logic, arXiv:2112.13627 [math.NT], 2021.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, arXiv preprint arXiv:1207.0404 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 17 2012
Vladimir Shevelev and Peter J. C. Moses, A family of digit functions with large periods, arXiv preprint arXiv:1209.5705 [math.NT], 2012.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, INTEGERS, Vol. 14 (2014) #64.
Eric Weisstein's World of Mathematics, Evil Number.
Index entries for sequences related to binary expansion of n
Index entries for "core" sequences

Complement of A000069 (the odious numbers). Cf. A133009.
a(n)=2*n+A010060(n)=A000069(n)-(-1)^A010060(n). Cf. A018900.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
Cf. A036585 (differences), A010060, A006364.
For primes see A027699, also A130593.
Cf. A006068, A048724, A059010, A094677.

a001969 n = a001969_list !! (n-1)
a001969_list = [x | x <- [0..], even $ a000120 x]
-- Reinhard Zumkeller, Feb 01 2012

[ n : n in [0..129] | IsEven(&+Intseq(n,2)) ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

s := proc(n) local i,j,ans; ans := [ ]; j := 0; for i from 0 while jA001969 := n->t1[n]; # s(k) gives first k terms.
# Alternative:
seq(`if`(add(k, k=convert(n,base,2))::even, n, NULL), n=0..129); # Peter Luschny, Jan 15 2021
# alternative for use outside this sequence
isA001969 := proc(n)
    add(d,d=convert(n,base,2)) ;
    type(%,'even') ;
end proc:
A001969 := proc(n)
    option remember ;
    local a;
    if n = 0 then
        1;
    else
        for a from procname(n-1)+1 do
            if isA001969(a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A001969(n),n=1..200) ; # R. J. Mathar, Aug 07 2022

Select[Range[0,300], EvenQ[DigitCount[ #, 2][[1]]] &]
a[ n_] := If[ n < 1, 0, With[{m = n - 1}, 2 m + Mod[-Total@IntegerDigits[m, 2], 2]]]; (* Michael Somos, Jun 09 2019 *)

a(n)=n-=1; 2*n+subst(Pol(binary(n)),x,1)%2

a(n)=if(n<1,0,if(n%2==0,a(n/2)+n,-a((n-1)/2)+3*n))

a(n)=2*(n-1)+hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 22 2013

def ok(n): return bin(n)[2:].count('1') % 2 == 0
print(list(filter(ok, range(130)))) # Michael S. Branicky, Jun 02 2021

from itertools import chain, count, islice
def A001969_gen(): # generator of terms
    return chain((0,),chain.from_iterable((sorted(n^ n<<1 for n in range(2**l,2**(l+1))) for l in count(0))))
A001969_list = list(islice(A001969_gen(),30)) # Chai Wah Wu, Jun 29 2022

def A001969(n): return ((m:=n-1).bit_count()&1)+(m<<1) # Chai Wah Wu, Mar 03 2023

a(n+1) - A001285(n) = 2n-1 has been verified for n <= 400. - John W. Layman, May 16 2003 [This can be directly verified by comparing Ralf Stephan's formulas for this sequence (see below) and for A001285. - Jianing Song, Nov 04 2024]
Note that 2n+1 is in the sequence iff 2n is not and so this sequence has asymptotic density 1/2. - Franklin T. Adams-Watters, Aug 23 2006
a(n) = (1/2) * (4n - 3 - (-1)^A000120(n-1)). - Ralf Stephan, Sep 14 2003
G.f.: Sum_{k>=0} (t(3+2t+3t^2)/(1-t^2)^2) * Product_{l=0..k-1} (1-x^(2^l)), where t = x^2^k. - Ralf Stephan, Mar 25 2004
a(2*n+1) + a(2*n) = A017101(n-1) = 8*n-5.
a(2*n) - a(2*n-1) gives the Thue-Morse sequence (3, 1 version): 3, 1, 1, 3, 1, 3, 3, 1, 1, 3, .... A001969(n) + A000069(n) = A016813(n-1) = 4*n-3. - Philippe Deléham, Feb 04 2004
a(1) = 0; for n > 1: a(n) = 3*n-3 - a(n/2) if n even, a(n) = a((n+1)/2)+n-1 if n odd.
Let b(n) = 1 if sum of digits of n is even, -1 if it is odd; then Shallit (1985) showed that Product_{n>=0} ((2n+1)/(2n+2))^b(n) = 1/sqrt(2).
a(n) = 2n - 2 + A010060(n-1). - Franklin T. Adams-Watters, Aug 28 2006
A005590(a(n-1)) <= 0. - Reinhard Zumkeller, Apr 11 2012
A106400(a(n-1)) = 1. - Reinhard Zumkeller, Apr 29 2012
a(n) = (a(n-1) + 2) XOR A010060(a(n-1) + 2). - Falk Hüffner, Jan 21 2022
a(n+1) = A006068(n) XOR (2*A006068(n)). - Rémy Sigrist, Apr 14 2022

More terms from Robin Trew (trew(AT)hcs.harvard.edu)

A007413 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

a(n)=2 if and only if n-1 is in A079523. - Benoit Cloitre, Mar 10 2003
Partial sums modulo 4 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, Mar 04 2004
To construct the sequence: start with 1 and concatenate 4 -1 = 3: 1, 3, then change the last term (2 -> 1, 3 ->2 ) gives 1, 2. Concatenate 1, 2 with 4 -1 = 3, 4 - 2 = 2: 1, 2, 3, 2 and change the last term: 1, 2, 3, 1. Concatenate 1, 2, 3, 1 with 4 - 1 = 3, 4 - 2 = 2, 4 - 3 = 1, 4 - 1 = 3: 1, 2, 3, 1, 3, 2, 1, 3 and change the last term: 1, 2, 3, 1, 3, 2, 1, 2 etc. - Philippe Deléham, Mar 04 2004
To construct the sequence: start with the Thue-Morse sequence A010060 = 0, 1, 1, 0, 1, 0, 0, 1, ... Then change 0 -> 1, 2, 3,  and 1 -> 3, 2, 1,  gives: 1, 2, 3, , 3, 2, 1, ,3, 2, 1, , 1, 2, 3, , 3, 2, 1, , ... and fill in the successive holes with the successive terms of the sequence itself. - _Philippe Deléham, Mar 04 2004
To construct the sequence: to insert the number 2 between the A003156(k)-th term and the (1 + A003156(k))-th term of the sequence 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, ... - Philippe Deléham, Mar 04 2004
Conjecture. The sequence is formed by the numbers of 1's between every pair of consecutive 2's in A076826. - Vladimir Shevelev, May 31 2009

			Here are the first 5 stages in the construction of this sequence, together with Mma code, taken from Keranen's article. His alphabet is a,b,c rather than 1,2,3.
productions = {"a" -> "abc ", "b" -> "ac ", "c" -> "b ", " " -> ""};
NestList[g, "a", 5] // TableForm
a
abc
abc ac b
abc ac b abc b ac
abc ac b abc b ac abc ac b ac abc b
abc ac b abc b ac abc ac b ac abc b abc ac b abc b ac abc b abc ac b ac

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, No. 7 (1906), 1-22.

Paolo Xausa, Table of n, a(n) for n = 1..10000
Roger L. Bagula, Description of sequence as successive rows of a triangle
James D. Currie, Non-repetitive words: Ages and essences, Combinatorica 16.1 (1996): 19-40. See p. 20.
James D. Currie, Palindrome positions in ternary square-free words, Theoretical Computer Science, 396 (2008) 254-257.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
V. Keranen, New Abelian Square-Free DT0L-Languages over 4 Letters, Theoretical Computer Science, Volume 410, Issues 38-40, 6 September 2009, Pages 3893-3900.
S. Kitaev and T. Mansour, Counting the occurrences of generalized patterns in words generated by a morphism, arXiv:math/0210170 [math.CO], 2002.
Andrzej Tomski and Maciej Zakarczemny, A note on Browkin's and Cao's cancellation algorithm, Technical Transections 7/2018.

Cf. A001285, A010060.
First differences of A000069.
Equals A036580(n-1) + 1.
Cf. A115384, A159481, A079523, A000120.

Nest[ Flatten[ # /. {1 -> {1, 2, 3}, 2 -> {1, 3}, 3 -> {2}}] &, {1}, 7] (* Robert G. Wilson v, May 07 2005 *)
2 - Differences[ThueMorse[Range[0, 100]]] (* Paolo Xausa, Oct 25 2024 *)

{a(n) = if( n<1 || valuation(n, 2)%2, 2, 2 + (-1)^subst( Pol(binary(n)), x,1))};

def A007413(n): return 2-(n.bit_count()&1)+((n-1).bit_count()&1) # Chai Wah Wu, Mar 03 2023

a(n) modulo 2 = A035263(n). a(A036554(n)) = 2. a(A003159(n)) = 1 if n odd. a(A003159(n)) = 3 if n even. a(n) = A033485(n) mod 4. a(n) = 4 - A036585(n-1). - Philippe Deléham, Mar 04 2004
a(n) = 2 - A029883(n) = 3 - A036577(n). - Philippe Deléham, Mar 20 2004
For n>=1, we have: 1) a(A108269(n))=A010684(n-1); 2) a(A079523(n))=A010684(n-1); 3) a(A081706(2n))=A010684(n). - Vladimir Shevelev, Jun 22 2009

A036577 Ternary Thue-Morse sequence: closed under a->abc, b->ac, c->b.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

nonn

Number of 1's between successive 0's in A010060.
The infinite sequence is abcacbabcbac... which is encoded with a->2, b->1, c->0 to produce this integer sequence.
From Jeffrey Shallit, Dec 07 2019: (Start)
This word is sometimes called 'vtm'; see, for example, see the Blanchet-Sadri et al. reference.
It is a squarefree word containing no instances of the factor 010 or 212 (or cbc, aba in the encoding).
Berstel proved many different definitions (e.g., Braunholtz, Istrail) of the word are equivalent. (End)

			2*x + x^2 + 2*x^4 + x^6 + 2*x^7 + x^8 + x^10 + 2*x^11 + 2*x^13 + x^14 + ...

M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 26.

G. C. Greubel, Table of n, a(n) for n = 1..10000
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.
J. Berstel, Sur la construction de mots sans carré, Sém. Théor. Nombres Bordeaux (1978--1979), 18.01-18.15.
F. Blanchet-Sadri, J. Currie, N. Fox, and N. Rampersad, Abelian complexity of fixed point of morphism 0 -> 012, 1 -> 02, 2 -> 1, INTEGERS 14 (2014), Paper A11.
C. Braunholtz, Advanced problem 5030: An infinite sequence of three symbols with no adjacent repeats, Amer. Math. Monthly 70 (1963), 675--676.
James D. Currie, Non-repetitive words: Ages and essences, Combinatorica 16.1 (1996): 19-40. See p. 21.
J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
David Hamm and Jeffrey Shallit, Characterization of finite and one-sided infinite fixed points of morphisms on free monoids, Technical Report CS-99-17, Dep. of Computer Science, University of Waterloo, 1999. See foot of page 2.
S. Istrail, On irreductible languages and nonrational numbers, Bull. Math. Soc. Sci. Math. R. S. Roumanie 21 (1977), 301-308.
Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
Pierre Popoli, Jeffrey Shallit, and Manon Stipulanti, Additive word complexity and Walnut, arXiv:2410.02409 [math.CO], 2024. See p. 13.
Michaël Rao, Michel Rigo, and Pavel Salimov, Avoiding 2-binomial squares and cubes, arXiv:1310.4743 [cs.FL], 2013.
Michaël Rao, Michel Rigo, and Pavel Salimov, Avoiding 2-binomial squares and cubes, Theoretical Computer Science, Volume 572, 23 March 2015, Pages 83-91.
Lukas Spiegelhofer, Gaps in the Thue-Morse word, arXiv:2102.01018 [math.CO], 2021.

Cf. A010059, A010060, A029883, A036585, A104248.

See A007413, A036580 for other versions.

(* ThueMorse is built-in since version 10.2, for lower versions it needs to be defined manually *) ThueMorse[n_] := Mod[DigitCount[n, 2, 1], 2]; Table[1 + ThueMorse[n] - ThueMorse[n-1], {n, 1, 100}]  (* Vladimir Reshetnikov, May 17 2016 *)
Nest[Flatten[# /. {2 -> {2, 1, 0}, 1 -> {2, 0}, 0 -> {1}}] &, {2, 1, 0}, 7] (* Robert G. Wilson v, Jul 30 2018 *)
Differences[ThueMorse[Range[0, 100]]] + 1 (* Paolo Xausa, Jul 17 2025 *)

{a(n) = if( n<1, 0, if( valuation( n, 2)%2, 1, 1 - (-1)^subst( Pol( binary(n)), x, 1)))} /* Michael Somos, Aug 03 2011 */

def A036577(n): return (n.bit_count()&1)+((n-1).bit_count()&1^1) # Chai Wah Wu, Mar 03 2023

a(n) = A036585(n) - 1 = A029883(n) + 1.
a(n) = 3 - A007413(n). a(A036554(n)) = 1; a(A091785(n)) = 0; a(A091855(n)) = 2. - Philippe Deléham, Mar 20 2004
a(4*n + 2) = 1. a(2*n + 1) = 2 * A010059(n). a(4*n + 3) = 2 * A010060(n). - Michael Somos, Aug 03 2011
a(n) = A010060(2*n - 1) + A010060(2*n) = A115384(2*n) - A115384(2*n - 2). - Zhuorui He, Jul 11 2025

A091855 Odious numbers (see A000069) in A003159.

Original entry on oeis.org

1, 4, 7, 11, 13, 16, 19, 21, 25, 28, 31, 35, 37, 41, 44, 47, 49, 52, 55, 59, 61, 64, 67, 69, 73, 76, 79, 81, 84, 87, 91, 93, 97, 100, 103, 107, 109, 112, 115, 117, 121, 124, 127, 131, 133, 137, 140, 143, 145, 148, 151, 155, 157, 161, 164, 167, 171, 173, 176, 179, 181

Offset: 1

Philippe Deléham, Mar 16 2004

Also n such that A033485(n) == 1 (mod 4); see A007413.
Also n such that A029883(n-1) = 1, A036577(n-1) = 2, A036585(n-1) = 3. - Philippe Deléham, Mar 25 2004
The number of odd numbers before the n-th even number in this sequence is a(n). - Philippe Deléham, Mar 27 2004
Numbers n such that {A010060(n-1), A010060(n)}={0,1} where A010060 is the Thue-Morse sequence. - Benoit Cloitre, Jun 16 2006
Positive integers not of the form n+A010060(n). - Jeffrey Shallit, Feb 13 2024

G. C. Greubel, Table of n, a(n) for n = 1..10000
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (2012), no. 1, 42-46.
Index entries for 2-automatic sequences.

A036554 := Select[Range[70500], OddQ[IntegerExponent[#, 2]] &]; Table[ A036554[[2*n - 1]]/2, {n, 1, 100}] (* G. C. Greubel, Jan 14 2018 *)

is(n)=hammingweight(n)%2 && valuation(n,2)%2==0 \\ Charles R Greathouse IV, May 09 2016

a(n) = A003159(2n-1) = A036554(2n-1)/2.
a(n) is asymptotic to 3*n - Benoit Cloitre, Mar 22 2004
A050292(a(n)) = 2n - 1. - Philippe Deléham, Mar 26 2004

More terms from Benoit Cloitre, Mar 22 2004

A029883 First differences of Thue-Morse sequence A001285.

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

N. J. A. Sloane, Dec 11 1999

Also first differences of {0,1} Thue-Morse sequence A010060.- N. J. A. Sloane, Jan 05 2021
Fixed point of the morphism a->abc, b->ac, c->b, with a = 1, b = 0, c = -1, starting with a(1) = 1. - Philippe Deléham
From Thomas Anton, Sep 22 2020: (Start)
This sequence, interpreted as an infinite word, is squarefree.
Let & represent concatenation. For a word w of integers, let -w be the same word with each symbol negated. Then, starting with the empty word, this sequence can be obtained by iteratively applying the transformation T(w) = w & 1 & -w & 0 & -w & -1 & w. (End)

G. C. Greubel, Table of n, a(n) for n = 1..10000
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.
G. N. Arzhantseva, C. H. Cashen, D. Gruber, and D. Hume, Contracting geodesics in infinitely presented graphical small cancellation groups, arXiv preprint arXiv:1602.03767 [math.GR], 2016-2017.
T. W. Cusick, H. Fredricksen and P. Stănică, On the delta sequence of the Thue-Morse sequence, Australas. J. Combin. 39 (2007), 293--300. [From _N. J. A. Sloane_, Dec 11 2009]
Florian Frohn and Jürgen Giesl, Proving Non-Termination by Acceleration Driven Clause Learning with LoAT, arXiv:2304.10166 [cs.LO], 2023.
Index entries for sequences that are fixed points of mappings

Apart from signs, same as A035263. Cf. A001285, A010060, A036554, A091785, A091855.

a(n+1) = A036577(n) - 1 = A036585(n) - 2.

Nest[ Function[ l, {Flatten[(l /. {0 -> {1, -1}, 1 -> {1, 0, -1}, -1 -> {0}})]}], {1}, 7] (* Robert G. Wilson v, Feb 26 2005 *)
ThueMorse /@ Range[0, 105] // Differences (* Jean-François Alcover, Oct 15 2019 *)

a(n)=if(n<1||valuation(n,2)%2,0,-(-1)^subst(Pol(binary(n)),x,1)) /* Michael Somos, Jul 08 2004 */

a(n)=hammingweight(n)%2-hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 26 2013

def A029883(n): return (bin(n).count('1')&1)-(bin(n-1).count('1')&1) # Chai Wah Wu, Mar 03 2023

Recurrence: a(4*n) = a(n), a(4*n+1) = a(2*n+1), a(4*n+2) = 0, a(4*n+3) = -a(2*n+1), starting a(1) = 1.
a(n) = 2 - A007413(n). a(A036554(n)) = 0; a(A091785(n)) = -1; a(A091855(n)) = 1. - Philippe Deléham, Mar 20 2004
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = -v+w+u^2-v^2+2*w^2-2*u*w. - Michael Somos, Jul 08 2004

Edited by Ralf Stephan, Dec 09 2004

A003156 A self-generating sequence (see Comments for definition).

Original entry on oeis.org

1, 4, 5, 6, 9, 12, 15, 16, 17, 20, 21, 22, 25, 26, 27, 30, 33, 36, 37, 38, 41, 44, 47, 48, 49, 52, 55, 58, 59, 60, 63, 64, 65, 68, 69, 70, 73, 76, 79, 80, 81, 84, 85, 86, 89, 90, 91, 94, 97, 100, 101, 102, 105, 106, 107, 110, 111, 112, 115, 118, 121, 122, 123, 126, 129, 132

Offset: 1

N. J. A. Sloane

nonn

From N. J. A. Sloane, Dec 26 2020: (Start)
The best definitions of the triple [this sequence, A003157, A003158] are as the rows a(n), b(n), c(n) of the table:
n: 1, 2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
a: 1, 4,  5,  6,  9, 12, 15, 16, 17, 20, 21, 22, ...
b: 3, 8, 11, 14, 19, 24, 29, 32, 35, 40, 43, 46, ...
c: 2, 7, 10, 13, 18, 23, 28, 31, 34, 39, 42, 45, ...
where a(1)=1, b(1)=3, c(1)=2, and thereafter
a(n) = mex{a(i), b(i), c(i), ib(n) = a(n) + 2*n,
c(n) = b(n) - 1.
Then a,b,c form a partition of the positive integers.
Note that there is another triple of sequences (A003144, A003145, A003146) also called a, b, c and also a partition of the positive integers, in a different paper by the same authors (Carlitz-Scovelle-Hoggatt) in the same volume of the same journal.
(End)
a(n) is the number of ones before the n-th zero in the Feigenbaum sequence A035263. - Philippe Deléham, Mar 27 2004
Number of odd numbers before the n-th even number in A007413, A007913, A001511, A029883, A033485, A035263, A036585, A065882, A065883, A088172, A092412. - Philippe Deléham, Apr 03 2004
Indices of a in the sequence closed under a -> abc, b -> a, c -> a, starting with a(1) = a; see A092606 where a = 0, b = 2, c = 1. - Philippe Deléham, Apr 12 2004

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

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]. See also Optimization, Discrete Mathematics and Applications to Data Sciences, Springer Optimization and Its Applications, Springer, Cham, 2025, and author's site, CNRS France, 2024. See p. 6.
L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., Fibonacci representations of higher order, Fib. Quart., 10 (1972), 43-69. [Here a, b, c are A003144, A003145, A003146.]
L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Representations for a special sequence, Fibonacci Quarterly 10.5 (1972), 499-518, 550. [A003156, A003157, A003158 are on page 500.]
Robbert Fokkink and Gandhar Joshi, On Cloitre's hiccup sequences, arXiv:2507.16956 [math.CO], 2025. See pp. 8, 17

Cf. A001511, A003157, A003158, A003159, A007413, A007913, A029883, A033485, A035263, A036554, A036585, A056196, A065882, A065883, A072939, A079523, A072939, A080426, A088172, A092412, A092606.

A091785 Evil numbers (see A001969) in A003159.

Original entry on oeis.org

3, 5, 9, 12, 15, 17, 20, 23, 27, 29, 33, 36, 39, 43, 45, 48, 51, 53, 57, 60, 63, 65, 68, 71, 75, 77, 80, 83, 85, 89, 92, 95, 99, 101, 105, 108, 111, 113, 116, 119, 123, 125, 129, 132, 135, 139, 141, 144, 147, 149, 153, 156, 159, 163, 165, 169, 172, 175, 177, 180, 183

Offset: 1

Philippe Deléham, Mar 16 2004

Also n such that A033485(n) == 3 (mod 4); see A007413.
Also n such that A029883(n-1) = -1, A036577(n-1) = 0, A036585(n-1) = 1. - Philippe Deléham, Mar 25 2004
The number of odd numbers before the n-th even number in this sequence is a(n). - Philippe Deléham, Mar 27 2004
Numbers n such that {A010060(n-1), A010060(n)}={1,0} where A010060 is the Thue-Morse sequence. - Benoit Cloitre, Jun 16 2006

G. C. Greubel, Table of n, a(n) for n = 1..10000
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (2012), pp. 42-46.
Index entries for 2-automatic sequences.

A036554 := Select[Range[750], OddQ[IntegerExponent[#, 2]] &]; Table[ A036554[[2*n]]/2, {n, 1, 50}] (* G. C. Greubel, Jan 14 2018 *)

is(n)=hammingweight(n-1)%2 && hammingweight(n)%2==0 \\ Charles R Greathouse IV, Mar 26 2013

a(n) = A003159(2*n) = A036554(2*n)/2.
a(n) is asymptotic to 3*n. - Benoit Cloitre, Mar 22 2004
A050292(a(n)) = 2n. - Philippe Deléham, Mar 26 2004

More terms from Benoit Cloitre, Mar 22 2004

A036578 Ternary Thue-Morse sequence: closed under a->abc, b->ac, c->b.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

nonn

Trajectory of 1 under the morphism 0 -> 12, 1 -> 102 & 2 -> 0. - Robert G. Wilson v, Apr 06 2008

Brian Hayes, Group Theory in the Bedroom and other Mathematical Diversions, Hill and Wang, A division of Farrar, Straus and Giroux, NY, 2008, pages 190-194.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 26.

Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (1) (2012) 42-46.
Index entries for sequences that are fixed points of mappings

Cf. A005679, A036577, A036579, A036580, A036581, A036582, A036583, A036584, A036585, A036586.

Nest[ # /. {0 -> {1, 2}, 1 -> {1, 0, 2}, 2 -> {0}} &, {0}, 7] // Flatten (* Robert G. Wilson v, Apr 06 2008 *)

Showing 1-8 of 8 results.

cp's OEIS Frontend

A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Formula

Extensions

A007413 A squarefree (or Thue-Morse) ternary sequence: closed under 1->123, 2->13, 3->2. Start with 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A036577 Ternary Thue-Morse sequence: closed under a->abc, b->ac, c->b.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A091855 Odious numbers (see A000069) in A003159.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Formula

Extensions

A029883 First differences of Thue-Morse sequence A001285.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A003156 A self-generating sequence (see Comments for definition).

Views

Author

Keywords

Comments