In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...
, 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 of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one).
The base-2 numeral system is a positional notatio ...
.
These numbers give the positions of the zero values in the
Thue–Morse sequence
In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) 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 number of 1s in its binary expansion.
In computer science, an odious number is said to have odd parity.
Examples
The first odious numbers are:
Properties
If a(n) denotes ...
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 that e ...
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, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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