

A001969


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


241



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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.
En français: les nombres païens.
a(n)A001285(n) = 2n1 has been verified for n=0..400.  John W. Layman
First differences give A036585. Observed by Franklin T. AdamsWatters, proved by Max Alekseyev, Aug 30 2006. This is equivalent to a(n) = 2*n + A010060(n). Proof: If the number of bits in n is odd then the last bit of a(n) is 1 and if the number of bits in n is even then the last bit of a(n) is 0. Hence the sequence of last bits is A010060. Therefore a(n) = 2*n + A010060(n).
Indices of zeros in the ThueMorse sequence A010060.  Tanya Khovanova, Feb 13 2009
A005590(a(n)) <= 0.  Reinhard Zumkeller, Apr 11 2012
A106400(a(n)) = 1.  Reinhard Zumkeller, Apr 29 2012
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 exclusiveor 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)


REFERENCES

H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
D. J. Newman, A Problem Seminar, Springer; see Problem #89.
V. S. Shevelev, On some identities connected with the partition of the positive integers with respect to the Morse sequence, Izv. Vuzov of the NorthCaucasus region, Nature sciences 4 (1997), 2123 (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
JeanPaul Allouche and Henri Cohen, Dirichlet series and curious infinite products, Bull. London Math. Soc. 17 (1985), 531538.
J.P. Allouche and J. Shallit, The ring of kregular sequences, Theoretical Computer Sci., 98 (1992), 163197.
J.P. Allouche, B. Cloitre, V. Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
J.P. Allouche, B. Cloitre, V. Shevelev, Beyond odious and evil, Aequationes mathematicae, March 2015, pp 113.
Chris Bernhardt, Evil twins alternate with odious twins, Math. Mag. 82 (2009), 5762.
J. N. Cooper, D. Eichhorn and K. O'Bryant, Reciprocals of binary power series, arXiv:math/0506496 [math.NT], 2005.
E. Fouvry, C. Mauduit, Sommes des chiffres et nombres presque premiers, (French) [Sums of digits and almost primes] Math. Ann. 305 (1996), no. 3, 571599. MR1397437 (97k:11029)
Sajed Haque, Chapter 3.2 of Discriminators of Integer Sequences, 2017, See p. 38.
Sajed Haque, Jeffrey Shallit, Discriminators and kRegular Sequences, 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. 2 (1959), 8589.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255261.
Jeffrey O. Shallit, On infinite products associated with sums of digits, J. Number Theory 21 (1985), 128134.
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
V. Shevelev and P. J. C. Moses, A family of digit functions with large periods, arXiv preprint arXiv:1209.5705 [math.NT], 2012
V. Shevelev and P. J. C. Moses, Tangent power sums and their applications, INTEGERS, 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

Note that 2n+1 is in the sequence iff 2n is not and so this sequence has asymptotic density 1/2.  Franklin T. AdamsWatters, Aug 23 2006
a(n) = (1/2) * (4n + 1  (1)^A000120(n)).  Ralf Stephan, Sep 14 2003
G.f.: Sum_{k>=0} (t(3+2t+3t^2)/(1t^2)^2) * Product_{l=0..k1} (1x^(2^l)), where t = x^2^k.  Ralf Stephan, Mar 25 2004
n such that A010060(n)=0.  Benoit Cloitre, Nov 15 2003
a(2*n+1) + a(2*n) = A017101(n) = 8*n+3. a(2*n+1)  a(2*n) gives the ThueMorse sequence (3, 1 version): 3, 1, 1, 3, 1, 3, 3, 1, 1, 3, .... A001969(n) + A000069(n) = A016813(n) = 4*n+1.  Philippe Deléham, Feb 04 2004
a(1) = 0; for n > 1: a(n) = 3*n3  a(n/2) if n even, a(n) = a((n+1)/2)+n1 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 + A010060(n).  Franklin T. AdamsWatters, Aug 28 2006


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.


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((n1)/2)+3*n))
(PARI) a(n)=2*(n1)+hammingweight(n1)%2 \\ Charles R Greathouse IV, Mar 22 2013
(MAGMA) [ n : n in [0..129]  IsEven(&+Intseq(n, 2)) ]; // Sergei Haller (sergei(AT)sergeihaller.de), Dec 21 2006
(Haskell)
a001969 n = a001969_list !! (n1)
a001969_list = [x  x < [0..], even $ a000120 x]
 Reinhard Zumkeller, Feb 01 2012


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



