Odious number

Number with odd number of 1s in binary

evil	odious
The first 16 evil and odious numbers in little-endian 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 number of 1s in its binary expansion. Non-negative integers that are not odious are called evil numbers.

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

Examples

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]

Properties

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

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

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
^ 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, S2CID 253596104
^ Morgenbesser, Johannes F.; Shallit, Jeffrey; Stoll, Thomas (2011), "Thue–Morse at multiples of an integer", Journal of Number Theory, 131 (8): 1498–1512, arXiv:1009.5357, doi:10.1016/j.jnt.2011.02.006, MR 2793891, S2CID 119309022
^ 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, MR 0104631

External links

Weisstein, Eric W., "Odious Number", MathWorld

Classes of natural numbers

Powers and related numbers
Achilles Power of 2 Power of 3 Power of 10 Square Cube Fourth power Fifth power Sixth power Seventh power Eighth power Perfect power Powerful Prime power

Of the form a × 2^b ± 1
Cullen Double Mersenne Fermat Mersenne Proth Thabit Woodall

Other polynomial numbers
Hilbert Idoneal Leyland Loeschian Lucky numbers of Euler

Recursively defined numbers
Fibonacci Jacobsthal Leonardo Lucas Narayana Padovan Pell Perrin

Possessing a specific set of other numbers
Amenable Congruent Knödel Riesel Sierpiński

Expressible via specific sums
Nonhypotenuse Polite Practical Primary pseudoperfect Ulam Wolstenholme

Figurate numbers

2-dimensional

centered	Centered triangular Centered square Centered pentagonal Centered hexagonal Centered heptagonal Centered octagonal Centered nonagonal Centered decagonal Star
non-centered	Triangular Square Square triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

3-dimensional

centered	Centered tetrahedral Centered cube Centered octahedral Centered dodecahedral Centered icosahedral
non-centered	Tetrahedral Cubic Octahedral Dodecahedral Icosahedral Stella octangula
pyramidal	Square pyramidal

4-dimensional

non-centered	Pentatope Squared triangular Tesseractic

Combinatorial numbers
Bell Cake Catalan Dedekind Delannoy Euler Eulerian Fuss–Catalan Lah Lazy caterer's sequence Lobb Motzkin Narayana Ordered Bell Schröder Schröder–Hipparchus Stirling first Stirling second Telephone number Wedderburn–Etherington

Primes
Wieferich Wall–Sun–Sun Wolstenholme prime Wilson

Pseudoprimes
Carmichael number Catalan pseudoprime Elliptic pseudoprime Euler pseudoprime Euler–Jacobi pseudoprime Fermat pseudoprime Frobenius pseudoprime Lucas pseudoprime Lucas–Carmichael number Perrin pseudoprime Somer–Lucas pseudoprime Strong pseudoprime

Arithmetic functions and dynamics

Divisor functions	Abundant Almost perfect Arithmetic Betrothed Colossally abundant Deficient Descartes Hemiperfect Highly abundant Highly composite Hyperperfect Multiply perfect Perfect Practical Primitive abundant Quasiperfect Refactorable Semiperfect Sublime Superabundant Superior highly composite Superperfect
Prime omega functions	Almost prime Semiprime
Euler's totient function	Highly cototient Highly totient Noncototient Nontotient Perfect totient Sparsely totient
Aliquot sequences	Amicable Perfect Sociable Untouchable
Primorial	Euclid Fortunate

Other prime factor or divisor related numbers
Blum Cyclic Erdős–Nicolas Erdős–Woods Friendly Giuga Harmonic divisor Jordan–Pólya Lucas–Carmichael Pronic Regular Rough Smooth Sphenic Størmer Super-Poulet Zeisel

Numeral system-dependent numbers

Arithmetic functions
and dynamics

Persistence
- Additive
- Multiplicative

Digit sum	Digit sum Digital root Self Sum-product
Digit product	Multiplicative digital root Sum-product
Coding-related	Meertens
Other	Dudeney Factorion Kaprekar Kaprekar's constant Keith Lychrel Narcissistic Perfect digit-to-digit invariant Perfect digital invariant Happy