Odious number

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. 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, and so on. If a ( n ) {\displaystyle a(n)} denotes the n {\displaystyle n} th odious number (with a ( 0 ) = 1 {\displaystyle a(0)=1} ), then for all n {\displaystyle n} , a ( a ( n ) ) = 2 a ( n ) {\displaystyle a(a(n))=2a(n)} . Every positive integer n {\displaystyle n} has an odious multiple that is at most n ( n + 4 ) {\displaystyle 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 2 r − 1 {\displaystyle n=2^{2r}-1} , such as 3, 15, 63, etc. For these numbers, the smallest odious multiple is exactly n ( n + 4 ) = 2 4 r + 2 2 r + 1 − 3 {\displaystyle n(n+4)=2^{4r}+2^{2r+1}-3} . The odious numbers give the positions of the non-zero values in the Thue–Morse sequence. Every power of two is odious, because its binary expansion has only one non-zero bit. Except for 3, every Mersenne prime is odious, because its binary expansion consists of an odd prime number of consecutive non-zero bits.