Odious number

In number theory, an odious number is a positive integer that has an odd number of 1s in its binary expansion.

The first odious numbers are:

1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38 ... ^[1]

These numbers give the positions of the nonzero values in the Thue–Morse sequence.

Non-negative integers that are not odious are called evil numbers. 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.^[2]

If $a(n)$ denotes the $n$ th odious number (with $a(0)=1$ ), then for all $n$ , $a(a(n))=2a(n)$ .^[3]

In computer science, an odious number is said to have odd parity.

References

^ Sloane, N. J. A. (ed.). "Sequence A000069 (Odious numbers: numbers with an odd number of 1's in their binary expansion)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ 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
^ Allouche, J.-P.; Cloitre, Benoit; Shevelev, V. (2016), "Beyond odious and evil", Aequationes Mathematicae, 90 (2): 341–353, doi:10.1007/s00010-015-0345-3, MR 3480513

External links

Odious Numbers

[1] Sloane, N. J. A. (ed.). "Sequence A000069 (Odious numbers: numbers with an odd number of 1's in their binary expansion)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[2] 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

[3] Allouche, J.-P.; Cloitre, Benoit; Shevelev, V. (2016), "Beyond odious and evil", Aequationes Mathematicae, 90 (2): 341–353, doi:10.1007/s00010-015-0345-3, MR 3480513

[1]

[2]

[3]