This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001969 Evil numbers: numbers with an even number of 1's in their binary expansion.
(Formerly M2395 N0952)

%I M2395 N0952

%S 0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,

%T 48,51,53,54,57,58,60,63,65,66,68,71,72,75,77,78,80,83,85,86,89,90,92,

%U 95,96,99,101,102,105,106,108,111,113,114,116,119,120,123,125,126,129

%N Evil numbers: numbers with an even number of 1's in their binary expansion.

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

%C En français: les nombres païens.

%C a(n)-A001285(n) = 2n-1 has been verified for n=0..400. - _John W. Layman_

%C First differences give A036585. Observed by _Franklin T. Adams-Watters_, 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).

%C Indices of zeros in the Thue-Morse sequence A010060. - _Tanya Khovanova_, Feb 13 2009

%C A005590(a(n)) <= 0. - _Reinhard Zumkeller_, Apr 11 2012

%C A106400(a(n)) = 1. - _Reinhard Zumkeller_, Apr 29 2012

%C 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

%D H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.

%D D. J. Newman, A Problem Seminar, Springer; see Problem #89.

%D V. 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).

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H N. J. A. Sloane, <a href="/A001969/b001969.txt">Table of n, a(n) for n = 1..10000</a>

%H Jean-Paul Allouche and Henri Cohen, <a href="http://dx.doi.org/10.1112/blms/17.6.531">Dirichlet series and curious infinite products</a>, Bull. London Math. Soc. 17 (1985), 531-538.

%H J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H J.-P. Allouche, B. Cloitre, V. Shevelev, <a href="http://arxiv.org/abs/1405.6214">Beyond odious and evil</a>, arXiv preprint arXiv:1405.6214 [math.NT], 2014.

%H J.-P. Allouche, B. Cloitre, V. Shevelev, <a href="http://www.math.bgu.ac.il/~shevelev/58_Beyond_J.pdf">Beyond odious and evil</a>, Aequationes mathematicae, March 2015, pp 1-13.

%H Chris Bernhardt, <a href="http://faculty.fairfield.edu/cbernhardt/evil%20twins.pdf">Evil twins alternate with odious twins</a>, Math. Mag. 82 (2009), 57--62.

%H J. N. Cooper, D. Eichhorn and K. O'Bryant, <a href="https://arxiv.org/abs/math/0506496">Reciprocals of binary power series</a>, arXiv:math/0506496 [math.NT], 2005.

%H E. Fouvry, C. Mauduit, <a href="http://dx.doi.org/10.1007/BF01444238">Sommes des chiffres et nombres presque premiers</a>, (French) [Sums of digits and almost primes] Math. Ann. 305 (1996), no. 3, 571--599. MR1397437 (97k:11029)

%H Sajed Haque, Chapter 3.2 of <a href="https://uwspace.uwaterloo.ca/bitstream/handle/10012/12234/Haque_Sajed.pdf">Discriminators of Integer Sequences</a>, 2017, See p. 38.

%H Sajed Haque, Jeffrey Shallit, <a href="http://arxiv.org/abs/1605.00092">Discriminators and k-Regular Sequences</a>, arXiv:1605.00092 [cs.DM], 2016.

%H Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.

%H J. Lambek and L. Moser, <a href="http://dx.doi.org/10.4153/CMB-1959-013-x">On some two way classifications of integers</a>, Canad. Math. Bull. 2 (1959), 85-89.

%H M. D. McIlroy, <a href="http://dx.doi.org/10.1137/0203020">The number of 1's in binary integers: bounds and extremal properties</a>, SIAM J. Comput., 3 (1974), 255-261.

%H Jeffrey O. Shallit, <a href="http://dx.doi.org/10.1016/0022-314X(85)90045-9">On infinite products associated with sums of digits</a>, J. Number Theory 21 (1985), 128-134.

%H Vladimir Shevelev and Peter J. C. Moses, <a href="http://arxiv.org/abs/1207.0404">Tangent power sums and their applications</a>, arXiv preprint arXiv:1207.0404 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 17 2012

%H V. Shevelev and P. J. C. Moses, <a href="http://arxiv.org/abs/1209.5705">A family of digit functions with large periods</a>, arXiv preprint arXiv:1209.5705 [math.NT], 2012

%H V. Shevelev and P. J. C. Moses, <a href="http://www.emis.de/journals/INTEGERS/papers/o64/o64.Abstract.html">Tangent power sums and their applications</a>, INTEGERS, 14(2014) #64.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EvilNumber.html">Evil Number</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F 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

%F a(n) = (1/2) * (4n + 1 - (-1)^A000120(n)). - _Ralf Stephan_, Sep 14 2003

%F 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

%F n such that A010060(n)=0. - _Benoit Cloitre_, Nov 15 2003

%F a(2*n+1) + a(2*n) = A017101(n) = 8*n+3. a(2*n+1) - a(2*n) gives the Thue-Morse 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

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

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

%F a(n) = 2n + A010060(n). - _Franklin T. Adams-Watters_, Aug 28 2006

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

%t Select[Range[0,300], EvenQ[DigitCount[ #, 2][[1]]] &]

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

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

%o (PARI) a(n)=2*(n-1)+hammingweight(n-1)%2 \\ _Charles R Greathouse IV_, Mar 22 2013

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

%o (Haskell)

%o a001969 n = a001969_list !! (n-1)

%o a001969_list = [x | x <- [0..], even $ a000120 x]

%o -- _Reinhard Zumkeller_, Feb 01 2012

%Y Complement of A000069 (the odious numbers). Cf. A133009.

%Y a(n)=2*n+A010060(n)=A000069(n)-(-1)^A010060(n). Cf. A018900.

%Y The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.

%Y Cf. A036585 (differences), A010060, A006364.

%Y For primes see A027699, also A130593.

%Y Cf. A059010.

%K easy,core,nonn,nice,base

%O 1,2

%A _N. J. A. Sloane_

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 22 17:25 EDT 2018. Contains 301072 sequences. (Running on oeis4.)