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')
.
4k, 4k+1, 4k+2, 4k+3
.) $\endgroup$ – greybeard Sep 1 '20 at 4:22