Odious number

Last updated March 04, 2024

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.

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]

Related Research Articles

2 (two) is a number, numeral and digit. It is the natural number following 1 and preceding 3. It is the smallest and only even prime number. Because it forms the basis of a duality, it has religious and spiritual significance in many cultures.

In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not divisible. For example, −4, 0, and 82 are even numbers, while −3, 5, 7, and 21 are odd numbers.

23 (twenty-three) is the natural number following 22 and preceding 24.

A power of two is a number of the form $2 n$ where $n$ is an integer, that is, the result of exponentiation with number two as the base and integer $n$ as the exponent.

63 (sixty-three) is the natural number following 62 and preceding 64.

1000 or one thousand is the natural number following 999 and preceding 1001. In most English-speaking countries, it can be written with or without a comma or sometimes a period separating the thousands digit: 1,000.

127 is the natural number following 126 and preceding 128. It is also a prime number.

In mathematics, the Thue–Morse sequence or Prouhet–Thue–Morse sequence or parity sequence is the binary sequence obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings 0 then 01, 0110, 01101001, 0110100110010110, and so on, which are prefixes of the Thue–Morse sequence. The full sequence begins:

126 is the natural number following 125 and preceding 127.

In mathematics, the Prouhet–Thue–Morse constant, named for Eugène Prouhet, Axel Thue, and Marston Morse, is the number—denoted by $τ$ —whose binary expansion 0.01101001100101101001011001101001... is given by the Prouhet–Thue–Morse sequence. That is,

1,000,000,000 is the natural number following 999,999,999 and preceding 1,000,000,001. With a number, "billion" can be abbreviated as b, bil or bn.

1023 is the natural number following 1022 and preceding 1024.

In number theory, a polite number is a positive integer that can be written as the sum of two or more consecutive positive integers. A positive integer which is not polite is called impolite. The impolite numbers are exactly the powers of two, and the polite numbers are the natural numbers that are not powers of two.

In number theory, an evil number is a non-negative integer that has an even number of 1s in its binary expansion. These numbers give the positions of the zero values in the Thue–Morse sequence, and for this reason they have also been called the Thue–Morse set. Non-negative integers that are not evil are called odious numbers.

5 (five) is a number, numeral and digit. It is the natural number, and cardinal number, following 4 and preceding 6, and is a prime number. It has garnered attention throughout history in part because distal extremities in humans typically contain five digits.

The Lambek–Moser theorem is a mathematical description of partitions of the natural numbers into two complementary sets. For instance, it applies to the partition of numbers into even and odd, or into prime and non-prime. There are two parts to the Lambek–Moser theorem. One part states that any two non-decreasing integer functions that are inverse, in a certain sense, can be used to split the natural numbers into two complementary subsets, and the other part states that every complementary partition can be constructed in this way. When a formula is known for the $th$ natural number in a set, the Lambek–Moser theorem can be used to obtain a formula for the $th$ number not in the set.

In number theory, a pernicious number is a positive integer such that the Hamming weight of its binary representation is prime, that is, there is a prime number of 1s when it is written as a binary number.

Gould's sequence is an integer sequence named after Henry W. Gould that counts how many odd numbers are in each row of Pascal's triangle. It consists only of powers of two, and begins:

In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4. Equivalently, they are the numbers whose binary representations are nonzero only in even positions.

In mathematics, the fibbinary numbers are the numbers whose binary representation does not contain two consecutive ones. That is, they are sums of distinct and non-consecutive powers of two.

References

↑ Sloane, N. J. A. (ed.), "SequenceA000069(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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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

[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, MR 3480513, S2CID 253596104

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

[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 , MR 0104631

[1]

[2]

[3]

[4]