A001969 - OEIS (original) (raw)

A001969

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

307

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

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.

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-1) + A010060(n-1).

Therefore the first differences of the present sequence equal 2 + first differences of A010060, which equals A036585. QED (End)

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

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

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.

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.

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)

Eric Weisstein's World of Mathematics, Evil Number.

FORMULA

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]

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

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

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:

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:

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

(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]

(Python)

def ok(n): return bin(n)[2:].count('1') % 2 == 0

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

(Python)

def A001969(n): return ((m:=n-1).bit_count()&1)+(m<<1) # Chai Wah Wu, Mar 03 2023

EXTENSIONS

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