View source for Odious number

{{Short description|Number with odd number of 1s in binary}}
{| class="wikitable" style="float: right; font-size: 80%; width: 230px;"
|style="padding: 5px; text-align: center; opacity: .5;"| [[File:First 16 evil numbers in big-endian binary.svg|80px]]<br>evil
|style="padding: 5px; text-align: center;"| [[File:First 16 odious numbers in big-endian binary.svg|80px]]<br>odious
|-
|colspan="2" style="word-wrap: break-word;"| The first 16 evil and odious numbers in binary. It can be seen, that both sequences differ only in the least significant bits, which form the Thue–Morse sequence for the evil, and its negation for the odious numbers. The other bits form the even numbers.
|}
In [[number theory]], an '''odious number''' is a positive integer that has an odd [[Hamming weight|number of 1s]] in its [[Binary number|binary expansion]]. [[Nonnegative integer]]s that are not odious are called [[evil numbers]].

In [[computer science]], an odious number is said to have [[Parity bit#Parity|odd parity]].

==Examples==
The first odious numbers are:
{{bi|left=1.6|1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38 ... <ref>{{Cite OEIS|A000069|name=Odious numbers: numbers with an odd number of 1's in their binary expansion|mode=cs2}}</ref>}}

==Properties==
If <math>a(n)</math> denotes the <math>n</math>th odious number (with <math>a(0)=1</math>), then for all <math>n</math>, <math>a(a(n))=2a(n)</math>.<ref>{{citation|last1=Allouche|first1=J.-P.|last2=Cloitre|first2=Benoit|last3=Shevelev|first3=V.|doi=10.1007/s00010-015-0345-3|doi-access=|issue=2|journal=[[Aequationes Mathematicae]]|mr=3480513|pages=341–353|title=Beyond odious and evil|volume=90|year=2016|s2cid=253596104 }}</ref>

Every positive integer <math>n</math> has an odious multiple that is at most <math>n(n+4)</math>. The numbers for which this bound is tight are exactly the [[Mersenne number]]s with even exponents, the numbers of the form <math>n = 2^{2r}-1</math>, such as 3, 15, 63, etc. For these numbers, the smallest odious multiple is exactly <math>n(n+4) = 2^{4r}+2^{2r+1}-3</math>.<ref>{{citation | last1 = Morgenbesser | first1 = Johannes F. | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | last3 = Stoll | first3 = Thomas | doi = 10.1016/j.jnt.2011.02.006 | doi-access=free | issue = 8 | journal = Journal of Number Theory | mr = 2793891 | pages = 1498–1512 | title = Thue–Morse at multiples of an integer | url = https://hal.archives-ouvertes.fr/hal-01278737 | volume = 131 | year = 2011| arxiv = 1009.5357 | s2cid = 119309022 }}</ref>

==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 [[multiset]]s of pairwise sums.<ref>{{citation|last1=Lambek|first1=J.|author1-link=Joachim Lambek|last2=Moser|first2=L.|author2-link=Leo Moser|doi=10.4153/CMB-1959-013-x|journal=[[Canadian Mathematical Bulletin]]|mr=104631|pages=85–89|title=On some two way classifications of integers|volume=2|year=1959|issue=2|doi-access=free}}</ref>

==References==
{{reflist}}

==External links==
{{Wikifunctions|Z15121|odious number checking}}
*{{mathworld|title=Odious Number|urlname=OdiousNumber|mode=cs2}}

{{Classes of natural numbers}}

[[Category:Integer sequences]]