evil number
{{Short description|Class of binary number}}
{{pp-semi-indef|small=yes}}
| class="wikitable" style="float: right; font-size: 80%; width: 230px;"
|style="padding: 5px; text-align: center;"| 80px |style="padding: 5px; text-align: center; opacity: .5;"| 80px |
| colspan="2" style="word-wrap: break-word;"| The first 16 evil and odious numbers in little-endian binary. It can be seen, that both sequences differ only in the least significant bits, which form the Thue–Morse sequence for the evil, and its negation for the odious numbers. The other bits form the even numbers. |
In number theory, an evil number is a non-negative integer that has an even number of 1s in its binary expansion.{{Cite OEIS|A001969|name=Evil numbers: numbers with an even number of 1's in their binary expansion|mode=cs2}} 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.{{citation|last1=Charlier|first1=Émilie|last2=Cisternino|first2=Célia|last3=Massuir|first3=Adeline|contribution=State complexity of the multiples of the Thue-Morse set|doi=10.4204/EPTCS.305.3|mr=4030092|pages=34–49|series=Electron. Proc. Theor. Comput. Sci. (EPTCS)|title=Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification|volume=305|year=2019|doi-access=free|arxiv=1903.06114}} Non-negative integers that are not evil are called odious numbers.
Examples
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.{{citation|last1=Lambek|first1=J.|author1-link=Joachim Lambek|last2=Moser|first2=L.|author2-link=Leo Moser|doi=10.4153/CMB-1959-013-x|journal=Canadian Mathematical Bulletin|mr=104631|pages=85–89|title=On some two way classifications of integers|volume=2|year=1959|issue=2 |doi-access=free}}
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.{{citation|last=Wright|first=E. M.|doi=10.2307/2309513|journal=American Mathematical Monthly|mr=104622|pages=199–201|title=Prouhet's 1851 solution of the Tarry-Escott problem of 1910|volume=66|year=1959|issue=3 |jstor=2309513 }}
In computer science
In computer science, an evil number is said to have even parity.