cp's OEIS Frontend

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

%I A001969 M2395 N0952 #255 Mar 18 2025 10:33:05
%S A001969 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 A001969 48,51,53,54,57,58,60,63,65,66,68,71,72,75,77,78,80,83,85,86,89,90,92,
%U A001969 95,96,99,101,102,105,106,108,111,113,114,116,119,120,123,125,126,129
%N A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.
%C A001969 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 A001969 In French: les nombres païens.
%C A001969 Theorem: First differences give A036585. (Observed by _Franklin T. Adams-Watters_.)
%C A001969 Proof from _Max Alekseyev_, Aug 30 2006 (edited by _N. J. A. Sloane_, Jan 05 2021): (Start)
%C A001969 Observe that if the last bit of a(n) is deleted, we get the nonnegative numbers 0, 1, 2, 3, ... in order.
%C A001969 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.
%C A001969 So, taking into account the different offsets here and in A010060, we have a(n) = 2*(n-1) + A010060(n-1).
%C A001969 Therefore the first differences of the present sequence equal 2 + first differences of A010060, which equals A036585.  QED (End)
%C A001969 Integers k such that A010060(k-1)=0. - _Benoit Cloitre_, Nov 15 2003
%C A001969 Indices of zeros in the Thue-Morse sequence A010060 shifted by 1. - _Tanya Khovanova_, Feb 13 2009
%C A001969 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
%C A001969 From _Charlie Neder_, Oct 07 2018: (Start)
%C A001969 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:
%C A001969 If the number of bits in a(n) is even, add a leading 0 so a(n) is 2k+1 bits long.
%C A001969 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)
%C A001969 Numbers of the form m XOR (2*m) for some m >= 0. - _Rémy Sigrist_, Feb 07 2021
%C A001969 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
%D A001969 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.
%D A001969 Hugh L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
%D A001969 Donald J. Newman, A Problem Seminar, Springer; see Problem #89.
%D A001969 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).
%D A001969 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001969 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001969 N. J. A. Sloane, <a href="/A001969/b001969.txt">Table of n, a(n) for n = 1..10000</a>
%H A001969 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., Vol. 17 (1985), pp. 531-538.
%H A001969 Jean-Paul Allouche and Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197; <a href="https://doi.org/10.1016/0304-3975(92)90001-V">DOI</a>.
%H A001969 Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, <a href="http://arxiv.org/abs/1405.6214">Beyond odious and evil</a>, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
%H A001969 Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, <a href="https://doi.org/10.1007/s00010-015-0345-3">Beyond odious and evil</a>, Aequationes mathematicae, Vol. 90 (2016), pp. 341-353; <a href="http://www.math.bgu.ac.il/~shevelev/58_Beyond_J.pdf">alternative link</a>.
%H A001969 Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, <a href="https://arxiv.org/abs/2401.13524">Combinatorics on words and generating Dirichlet series of automatic sequences</a>, arXiv:2401.13524 [math.CO], 2025. See p. 19.
%H A001969 Chris Bernhardt, <a href="https://www.jstor.org/stable/27643161">Evil twins alternate with odious twins</a>, Math. Mag., Vol. 82, No. 1 (2009), pp. 57-62; <a href="https://web.archive.org/web/20181126095925/http://faculty.fairfield.edu/cbernhardt/evil%20twins.pdf">alternative link</a>.
%H A001969 Joshua N. Cooper, Dennis Eichhorn and Kevin O'Bryant, <a href="https://doi.org/10.1142/S1793042106000693">Reciprocals of binary power series</a>, International Journal of Number Theory, Vol. 2, No. 4 (2006), pp. 499-522; <a href="https://arxiv.org/abs/math/0506496">arXiv preprint</a>, arXiv:math/0506496 [math.NT], 2005.
%H A001969 Aviezri S. Fraenkel, <a href="https://doi.org/10.1016/j.disc.2011.03.032">The vile, dopey, evil and odious game players</a>, Discrete Math., Vol. 312, No. 1 (2012), pp. 42-46.
%H A001969 E. Fouvry and 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., Vol. 305, No. 3 (1996), pp. 571-599. MR1397437 (97k:11029)
%H A001969 Sajed Haque, Chapter 3.2 of <a href="https://uwspace.uwaterloo.ca/bitstream/handle/10012/12234/Haque_Sajed.pdf">Discriminators of Integer Sequences</a>, thesis, University of Waterloo, Ontario, Canada, 2017. See p. 38.
%H A001969 Sajed Haque and Jeffrey Shallit, <a href="http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/q76/q76.pdf">Discriminators and k-Regular Sequences</a> Integers, Vol. 16 (2016), Article A76; <a href="https://arxiv.org/abs/1605.00092">arXiv preprint</a>, arXiv:1605.00092 [cs.DM], 2016.
%H A001969 Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.
%H A001969 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., Vol. 2, No. 2 (1959), pp. 85-89.
%H A001969 P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, <a href="https://arxiv.org/abs/2201.06636">On digital sequences associated with Pascal's triangle</a>, arXiv:2201.06636 [math.NT], 2022.
%H A001969 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., Vol. 3, No. 4 (1974), pp. 255-261.
%H A001969 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, Vol. 21, No. 2 (1985), pp. 128-134.
%H A001969 Jeffrey Shallit, <a href="https://arxiv.org/abs/2103.10904">Frobenius Numbers and Automatic Sequences</a>, arXiv:2103.10904 [math.NT], 2021.
%H A001969 Jeffrey Shallit, <a href="https://arxiv.org/abs/2112.13627">Additive Number Theory via Automata and Logic</a>, arXiv:2112.13627 [math.NT], 2021.
%H A001969 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 A001969 Vladimir Shevelev and Peter 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 A001969 Vladimir Shevelev and Peter J. C. Moses, <a href="http://www.emis.de/journals/INTEGERS/papers/o64/o64.Abstract.html">Tangent power sums and their applications</a>, INTEGERS, Vol. 14 (2014) #64.
%H A001969 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/EvilNumber.html">Evil Number</a>.
%H A001969 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H A001969 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A001969 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]
%F A001969 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 A001969 a(n) = (1/2) * (4n - 3 - (-1)^A000120(n-1)). - _Ralf Stephan_, Sep 14 2003
%F A001969 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 A001969 a(2*n+1) + a(2*n) = A017101(n-1) = 8*n-5.
%F A001969 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
%F A001969 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 A001969 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 A001969 a(n) = 2n - 2 + A010060(n-1). - _Franklin T. Adams-Watters_, Aug 28 2006
%F A001969 A005590(a(n-1)) <= 0. - _Reinhard Zumkeller_, Apr 11 2012
%F A001969 A106400(a(n-1)) = 1. - _Reinhard Zumkeller_, Apr 29 2012
%F A001969 a(n) = (a(n-1) + 2) XOR A010060(a(n-1) + 2). - _Falk Hüffner_, Jan 21 2022
%F A001969 a(n+1) = A006068(n) XOR (2*A006068(n)). - _Rémy Sigrist_, Apr 14 2022
%p A001969 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.
%p A001969 # Alternative:
%p A001969 seq(`if`(add(k, k=convert(n,base,2))::even, n, NULL), n=0..129); # _Peter Luschny_, Jan 15 2021
%p A001969 # alternative for use outside this sequence
%p A001969 isA001969 := proc(n)
%p A001969     add(d,d=convert(n,base,2)) ;
%p A001969     type(%,'even') ;
%p A001969 end proc:
%p A001969 A001969 := proc(n)
%p A001969     option remember ;
%p A001969     local a;
%p A001969     if n = 0 then
%p A001969         1;
%p A001969     else
%p A001969         for a from procname(n-1)+1 do
%p A001969             if isA001969(a) then
%p A001969                 return a;
%p A001969             end if;
%p A001969         end do:
%p A001969     end if;
%p A001969 end proc:
%p A001969 seq(A001969(n),n=1..200) ; # _R. J. Mathar_, Aug 07 2022
%t A001969 Select[Range[0,300], EvenQ[DigitCount[ #, 2][[1]]] &]
%t A001969 a[ n_] := If[ n < 1, 0, With[{m = n - 1}, 2 m + Mod[-Total@IntegerDigits[m, 2], 2]]]; (* _Michael Somos_, Jun 09 2019 *)
%o A001969 (PARI) a(n)=n-=1; 2*n+subst(Pol(binary(n)),x,1)%2
%o A001969 (PARI) a(n)=if(n<1,0,if(n%2==0,a(n/2)+n,-a((n-1)/2)+3*n))
%o A001969 (PARI) a(n)=2*(n-1)+hammingweight(n-1)%2 \\ _Charles R Greathouse IV_, Mar 22 2013
%o A001969 (Magma) [ n : n in [0..129] | IsEven(&+Intseq(n,2)) ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
%o A001969 (Haskell)
%o A001969 a001969 n = a001969_list !! (n-1)
%o A001969 a001969_list = [x | x <- [0..], even $ a000120 x]
%o A001969 -- _Reinhard Zumkeller_, Feb 01 2012
%o A001969 (Python)
%o A001969 def ok(n): return bin(n)[2:].count('1') % 2 == 0
%o A001969 print(list(filter(ok, range(130)))) # _Michael S. Branicky_, Jun 02 2021
%o A001969 (Python)
%o A001969 from itertools import chain, count, islice
%o A001969 def A001969_gen(): # generator of terms
%o A001969     return chain((0,),chain.from_iterable((sorted(n^ n<<1 for n in range(2**l,2**(l+1))) for l in count(0))))
%o A001969 A001969_list = list(islice(A001969_gen(),30)) # _Chai Wah Wu_, Jun 29 2022
%o A001969 (Python)
%o A001969 def A001969(n): return ((m:=n-1).bit_count()&1)+(m<<1) # _Chai Wah Wu_, Mar 03 2023
%Y A001969 Complement of A000069 (the odious numbers). Cf. A133009.
%Y A001969 a(n)=2*n+A010060(n)=A000069(n)-(-1)^A010060(n). Cf. A018900.
%Y A001969 The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
%Y A001969 Cf. A036585 (differences), A010060, A006364.
%Y A001969 For primes see A027699, also A130593.
%Y A001969 Cf. A006068, A048724, A059010, A094677.
%K A001969 easy,core,nonn,nice,base
%O A001969 1,2
%A A001969 _N. J. A. Sloane_
%E A001969 More terms from Robin Trew (trew(AT)hcs.harvard.edu)