In
number theory, 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, 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
multisets 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 of finding sets of numbers whose sums of powers are equal up to the
th power.
In computer science
In
computer science, an evil number is said to have
even parity.
References
{{Classes of natural numbers
Integer sequences