Evil number

In number theory, an evil number is a non-negative integer that has an even number of 1s in its binary expansion.[1] 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.[2] Non-negative integers that are not evil are called odious numbers.

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 ...[1]

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.[3]

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.[4]

In computer science

In computer science, an evil number is said to have even parity.

gollark: Regular user, TU, moderator, admin.
gollark: In practice I think there are probably only about, what, four?
gollark: It's just very hot and big, and doesn't produce coherent light.
gollark: It is not, technically, a *laser*, as far as I know.
gollark: If you were at the centre of the moon or something, that would probably work somewhat as thermal shielding just because of how big those things are, so it would at least take a while for enough heat to reach you that it'd be a problem.

References
  1. 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.
  2. 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
  3. 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
  4. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.