# Efficient Algorithm to Find the n-th Odious Number

An odious number is defined as an integer that has odd binary Hamming weight. I need an implementation of algorithm that finds the nth odious number, preferably recursive. Any ideas? A python script is also wanted, but I can write it myself once the algorithm is found.

More description can be found on formula section in OEIS: A000069.

• (Concentrate on 4k, 4k+1, 4k+2, 4k+3.) – greybeard Sep 1 '20 at 4:22

## 2 Answers

Here is the recursive formula for odious numbers, \begin{align} a_1&=1,\\ a_{2n} &= 6n-3 -a_n,\\ a_{2n+1} &= a_{n+1} + 2n. \end{align} The formula can be proved easily by observing, as greybeard pointed out, there is exactly one odious number among $$2k-1, 2k$$ for all positive integer $$k$$.

Here is a simple algorithm in Python to compute the $$n$$-th odious number.

def odious_number(n):
if n == 1:
return 1
if n % 2 == 0:
return 3 * (n - 1) - odious_number(n // 2)
else:
return odious_number((n + 1) // 2) + n - 1

if __name__ == "__main__":
for i in range(1, 16):
print(odious_number(i), end=", ")
# Output: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28,


There is also a "closed" formula. $$a_n = 2n - 1 - \text{hamming_weight}(n - 1)\ \%\ 2$$

So, we have the following one-liner.

def odious_number(n):
return 2 * n - 1 - (n - 1).bit_count() % 2


int.bit_count(), which returns the Hamming weight of an integer, is available since Python 3.10. Before that version of Python, we can use, for example, bin(i).count('1').

• Yuval's answer shows how to prove the "closed" formula immediately. Be advised that he counts 1 as the 0-th odious number, while 1 is the first odious number in this answer. – John L. Sep 1 '20 at 13:52

Here is an alternative answer, following greybeard's advice. For each $$k$$, the two integers $$2k,2k+1$$ contain exactly one odious number. Hence the $$i$$th odious number is either $$2i$$ or $$2i+1$$: it is $$2i$$ if $$i$$ itself is odious, and $$2i+1$$ otherwise.

Stated differently, the $$i$$th odious number is $$2i+1-b$$, where $$b$$ is the parity of the number of ones in $$i$$.