Efficient Algorithm to Find the n-th Odious Number

Question

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.

Answer 1

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').}

Answer 2

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$.