%I M2395 N0952 #246 Dec 31 2023 00:26:09
%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: nonnegative integers 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 In French: les nombres païens.
%C Theorem: First differences give A036585. (Observed by _Franklin T. Adams-Watters_.)
%C Proof from _Max Alekseyev_, Aug 30 2006 (edited by _N. J. A. Sloane_, Jan 05 2021): (Start)
%C Observe that if the last bit of a(n) is deleted, we get the nonnegative numbers 0, 1, 2, 3, ... in order.
%C 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 So, taking into account the different offsets here and in A010060, we have a(n) = 2*(n-1) + A010060(n-1).
%C Therefore the first differences of the present sequence equal 2 + first differences of A010060, which equals A036585. QED (End)
%C Integers k such that A010060(k-1)=0. - _Benoit Cloitre_, Nov 15 2003
%C Indices of zeros in the Thue-Morse sequence A010060 shifted by 1. - _Tanya Khovanova_, Feb 13 2009
%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
%C From _Charlie Neder_, Oct 07 2018: (Start)
%C 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 If the number of bits in a(n) is even, add a leading 0 so a(n) is 2k+1 bits long.
%C 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 Numbers of the form m XOR (2*m) for some m >= 0. - _Rémy Sigrist_, Feb 07 2021
%C 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 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 Hugh L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
%D Donald J. Newman, A Problem Seminar, Springer; see Problem #89.
%D 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 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., Vol. 17 (1985), pp. 531-538.
%H 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 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 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 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 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 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 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 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 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 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., Vol. 2, No. 2 (1959), pp. 85-89.
%H 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 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 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 Jeffrey Shallit, <a href="https://arxiv.org/abs/2103.10904">Frobenius Numbers and Automatic Sequences</a>, arXiv:2103.10904 [math.NT], 2021.
%H 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 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 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 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 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 a(n+1) - A001285(n) = 2n-1 has been verified for n <= 400. - _John W. Layman_, May 16 2003
%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 - 3 - (-1)^A000120(n-1)). - _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 a(2*n+1) + a(2*n) = A017101(n-1) = 8*n-5.
%F 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 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 - 2 + A010060(n-1). - _Franklin T. Adams-Watters_, Aug 28 2006
%F A005590(a(n-1)) <= 0. - _Reinhard Zumkeller_, Apr 11 2012
%F A106400(a(n-1)) = 1. - _Reinhard Zumkeller_, Apr 29 2012
%F a(n) = (a(n-1) + 2) XOR A010060(a(n-1) + 2). - _Falk Hüffner_, Jan 21 2022
%F a(n+1) = A006068(n) XOR (2*A006068(n)). - _Rémy Sigrist_, Apr 14 2022
%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.
%p # Alternative:
%p seq(`if`(add(k, k=convert(n,base,2))::even, n, NULL), n=0..129); # _Peter Luschny_, Jan 15 2021
%p # alternative for use outside this sequence
%p isA001969 := proc(n)
%p add(d,d=convert(n,base,2)) ;
%p type(%,'even') ;
%p end proc:
%p A001969 := proc(n)
%p option remember ;
%p local a;
%p if n = 0 then
%p 1;
%p else
%p for a from procname(n-1)+1 do
%p if isA001969(a) then
%p return a;
%p end if;
%p end do:
%p end if;
%p end proc:
%p seq(A001969(n),n=1..200) ; # _R. J. Mathar_, Aug 07 2022
%t Select[Range[0,300], EvenQ[DigitCount[ #, 2][[1]]] &]
%t a[ n_] := If[ n < 1, 0, With[{m = n - 1}, 2 m + Mod[-Total@IntegerDigits[m, 2], 2]]]; (* _Michael Somos_, Jun 09 2019 *)
%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
%o (Python)
%o def ok(n): return bin(n)[2:].count('1') % 2 == 0
%o print(list(filter(ok, range(130)))) # _Michael S. Branicky_, Jun 02 2021
%o (Python)
%o from itertools import chain, count, islice
%o def A001969_gen(): # generator of terms
%o 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_list = list(islice(A001969_gen(),30)) # _Chai Wah Wu_, Jun 29 2022
%o (Python)
%o def A001969(n): return ((m:=n-1).bit_count()&1)+(m<<1) # _Chai Wah Wu_, Mar 03 2023
%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. A006068, A048724, A059010, A094677.
%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)