Classification of numbers on the base of binary representation

Question

The problem is the following. I would like to find a simple algorithm or principle of classification of numbers regarding their presentation in binary form.

Let's consider an example. The numbers by 4-digit binary numbers are following:

$0000_2=0$

$0001_2=1$

$0010_2=2$

$\vdots $

$1111_2=15$

I need to divide the set {0,1,...,15} into subsets, each member of which can be presented by certain numbers of binary ones in binary representation.

I.e.

$C_0=\{0\}$ ($0$ binary ones)

$C_1=\{1, 2, 4, 8\}$ (1 binary one: $0001_2$, $0010_2$, $0100_2$, $1000_2$)

$C_2= \{3, 5, 6, 9, 10, 12\}$ (2 binary ones)

$\vdots $

$C_5=\{ 15 \}$

Does there exist a result from the number theory allowing to reveal these subsets without transition to binary representation?

Answer 1

The number of ones in the binary representation of $n$ is the greatest integer $r$ such that $2^r$ divides $$\binom{2n}n$$

See https://oeis.org/A000120

It is not too hard (but not too simple, either) to prove this by induction.

Answer 2

If you're doing this on a computer, it seems kind of strange to me that you want to bypass the binary representation of the numbers.

But I'll try. Another user already mentioned Sloane's A000120, which includes this recurrence relation: $a(0) = 0, a(2n) = a(n), a(2n + 1) = a(n) + 1$. If your subset starts on $0$ or a power of $2$ and runs consecutively through a number of the form $2^k -1$, it might be practical to run through the recurrence relation for those numbers and then sort them according to the results.

Also notice the following facts, some more obvious than others:

• Only $0$ has a binary weight of $0$.
• The numbers with a binary weight of $1$ are the powers of $2$ (thus $1, 2, 4, 8$).
• All numbers of the form $3 \times 2^k$, $5 \times 2^k$ or $9 \times 2^k$ for $k \geq 0$ have a binary weight of $2$ ($3, 5, 6, 9, 10, 12$; there are other numbers with this same weight, but no more in the range $0$ to $15$).
• The primes $7$, $11$, $13$ have a binary weight of $3$. Also $14 = 7 \times 2$.
• $15$ has a binary weight of $4$.

The main take-away from this is that if have one number with a certain binary weight, you can find infinitely many more numbers with that same binary weight by the simple action of multiplying by powers of $2$. But to find all numbers with that binary weight within a given finite range, you have to find all "primitive" combinations of the necessary number of on bits with the appropriate number of off bits inserted (by "primitive" here I mean odd).