A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion. (Formerly M2395 N0952)

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

Comments

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 - 2 + 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

References

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

Links

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.

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

Formula

a(n) - A001285(n) = 2n-1 has been verified for n <= 400. - John W. Layman

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

Maple

s := proc(n) local i, j, ans; ans := [ ]; j := 0; for i from 0 while j<n do if add(k, k=convert(i, base, 2)) mod 2=0 then ans := [ op(ans), i ]; j := j+1; fi; od; RETURN(ans); end; t1 := s(100); A001969 := 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

Mathematica

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

Prog

(PARI) a(n)=n-=1; 2*n+subst(Pol(binary(n)), x, 1)%2
(PARI) a(n)=if(n<1, 0, if(n%2==0, a(n/2)+n, -a((n-1)/2)+3*n))
(PARI) a(n)=2*(n-1)+hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 22 2013
(Magma) [ n : n in [0..129] | IsEven(&+Intseq(n, 2)) ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
(Haskell)
a001969 n = a001969_list !! (n-1)
a001969_list = [x | x <- [0..], even $ a000120 x]
-- Reinhard Zumkeller, Feb 01 2012
(Python)
def ok(n): return bin(n)[2:].count('1') % 2 == 0
print(list(filter(ok, range(130)))) # Michael S. Branicky, Jun 02 2021
(Python)
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
(Python)
def A001969(n): return ((m:=n-1).bit_count()&1)+(m<<1) # Chai Wah Wu, Mar 03 2023

Crossrefs

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.

Sequence in context: A165740 A241571 A080307 * A075311 A032786 A080309

Adjacent sequences: A001966 A001967 A001968 * A001970 A001971 A001972

Keyword

easy,core,nonn,nice,base

Author

N. J. A. Sloane

Extensions

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

Status

approved