Evil number

From HandWiki
Short description: Class of binary number

In number theory, an evil number is a non-negative integer that has an even number of 1s in its binary expansion.[1] These numbers give the positions of the zero values in the Thue–Morse sequence, and for this reason they have also been called the Thue–Morse set.[2] Non-negative integers that are not evil are called odious numbers.


The first evil numbers are:

0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39 ...[1]

Equal sums

The partition of the non-negative integers into the odious and evil numbers is the unique partition of these numbers into two sets that have equal multisets of pairwise sums.[3]

As 19th-century mathematician Eugène Prouhet showed, the partition into evil and odious numbers of the numbers from [math]\displaystyle{ 0 }[/math] to [math]\displaystyle{ 2^k-1 }[/math], for any [math]\displaystyle{ k }[/math], provides a solution to the Prouhet–Tarry–Escott problem of finding sets of numbers whose sums of powers are equal up to the [math]\displaystyle{ k }[/math]th power.[4]

In computer science

In computer science, an evil number is said to have even parity.


  1. 1.0 1.1 Sloane, N. J. A., ed. "Sequence A001969 (Evil numbers: numbers with an even number of 1's in their binary expansion)". OEIS Foundation. https://oeis.org/A001969. 
  2. Charlier, Émilie; Cisternino, Célia; Massuir, Adeline (2019), "State complexity of the multiples of the Thue-Morse set", Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification, Electron. Proc. Theor. Comput. Sci. (EPTCS), 305, pp. 34–49, doi:10.4204/EPTCS.305.3 
  3. Lambek, J.; Moser, L. (1959), "On some two way classifications of integers", Canadian Mathematical Bulletin 2 (2): 85–89, doi:10.4153/CMB-1959-013-x 
  4. Wright, E. M. (1959), "Prouhet's 1851 solution of the Tarry-Escott problem of 1910", American Mathematical Monthly 66 (3): 199–201, doi:10.2307/2309513