Odious number

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 denotes the th odious number (with ), then for all , .[3]

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

References[edit]

  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

External links[edit]