Odious number

From HandWiki
Short description: Number with odd number of 1s in binary

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.


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]


If [math]\displaystyle{ a(n) }[/math] denotes the [math]\displaystyle{ n }[/math]th odious number (with [math]\displaystyle{ a(0)=1 }[/math]), then for all [math]\displaystyle{ n }[/math], [math]\displaystyle{ a(a(n))=2a(n) }[/math].[2]

Every positive integer [math]\displaystyle{ n }[/math] has an odious multiple that is at most [math]\displaystyle{ n(n+4) }[/math]. The numbers for which this bound is tight are exactly the Mersenne numbers with even exponents, the numbers of the form [math]\displaystyle{ n = 2^{2r}-1 }[/math], such as 3, 15, 63, etc. For these numbers, the smallest odious multiple is exactly [math]\displaystyle{ n(n+4) = 2^{4r}+2^{2r+1}-3 }[/math].[3]

Related sequences

The odious numbers give the positions of the nonzero values in the Thue–Morse sequence. Every power of two is odious, because its binary expansion has only one nonzero bit. Except for 3, every Mersenne prime is odious, because its binary expansion consists of an odd prime number of consecutive nonzero bits.

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

Any pernicious number is either odious or of the form [math]\displaystyle{ 2^n+1 }[/math] for [math]\displaystyle{ n\gt 0 }[/math].


  1. Sloane, N. J. A., ed. "Sequence A000069 (Odious numbers: numbers with an odd number of 1's in their binary expansion)". OEIS Foundation. https://oeis.org/A000069. 
  2. 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 
  3. Morgenbesser, Johannes F.; Shallit, Jeffrey; Stoll, Thomas (2011), "Thue–Morse at multiples of an integer", Journal of Number Theory 131 (8): 1498–1512, doi:10.1016/j.jnt.2011.02.006, https://hal.archives-ouvertes.fr/hal-01278737 
  4. Lambek, J.; Moser, L. (1959), "On some two way classifications of integers", Canadian Mathematical Bulletin 2 (2): 85–89, doi:10.4153/CMB-1959-013-x 

External links