In number theory, an evil number is a non-negative integer that has an even number of 1s in its binary expansion. 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. 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 ...
As 19th-century mathematician Eugène Prouhet showed, the partition into evil and odious numbers of the numbers from to , for any , provides a solution to the Prouhet–Tarry–Escott problem of finding sets of numbers whose sums of powers are equal up to the th power.
In computer science
- Sloane, N. J. A. (ed.). "Sequence A001969 (Evil numbers: numbers with an even number of 1's in their binary expansion)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- 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, MR 4030092
- Lambek, J.; Moser, L. (1959), "On some two way classifications of integers", Canadian Mathematical Bulletin, 2: 85–89, doi:10.4153/CMB-1959-013-x, MR 0104631
- Wright, E. M. (1959), "Prouhet's 1851 solution of the Tarry-Escott problem of 1910", American Mathematical Monthly, 66: 199–201, doi:10.2307/2309513, MR 0104622