In
number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, an evil number is a non-negative integer that has an even
number of 1s in its
binary expansion
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method for representing numbers that uses only two symbols for the natural numbers: typically "0" ( zero) and "1" ( one). A ''binary number'' may als ...
.
These numbers give the positions of the zero values in the
Thue–Morse sequence
In mathematics, the Thue–Morse or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of 0s and 1s) that can be obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...
, and for this reason they have also been called the Thue–Morse set. Non-negative integers that are not evil are called
odious number
In number theory, an odious number is a positive integer that has an odd Hamming weight, number of 1s in its Binary number, binary expansion. Nonnegative integers that are not odious are called evil numbers.
In computer science, an odious number ...
s.
Examples
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 ...
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
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the ''multiplicity'' of ...
s of pairwise sums.
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 In mathematics, the Prouhet–Tarry–Escott problem asks for two disjoint multisets ''A'' and ''B'' of ''n'' integers each, whose first ''k'' power sum symmetric polynomials are all equal.
That is, the two multisets should satisfy the equations
:\ ...
of finding sets of numbers whose sums of powers are equal up to the
th power.
In computer science
In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, an evil number is said to have
even parity
A parity bit, or check bit, is a bit added to a string of binary code. Parity bits are a simple form of error detecting code. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit octets (bytes), ...
.
References
{{Classes of natural numbers
Integer sequences