5
$\begingroup$

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.

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

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – John L. Sep 1 '20 at 13:52
5
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.