How do I find the nth number that has two 1's in its binary representation?

Question

I'm trying to find the a closed-form equation for the nth number that has exactly two 1's in its binary representation. The first few numbers are 3, 5, 6, 9, 10, 12, 17, 18, and so on.

My first thought was to use generating functions, and through some experimenting, I found the recursive formula $a_n=2a_{n-1}+2^{\lfloor log_2(a_{n-1}) \rfloor}$ which is a bit of a mess

I eventually got $$A(x) = \sum_{n=1}^{\infty} 3(2x)^n + \sum_{n=1}^{\infty} \frac{2^{\lfloor log_2(a_{n-1}) \rfloor}}{1-2x}x^n$$ where $A(x)$ is the generating function.

I'm stuck at this point and am not sure where to go from here

Answer 1

The numbers are of the form $2^n+2^k$ for $0\leq k<n.$ With $(n,k)$ before $(n',k')$ of $n>n'$ or $n=n'$ and $k>k'.$

So this means finding a way to calculate the series:

$$1\to(1,0),2\to(2,0),3\to(2,1),4\to(3,0),\dots.$$

Now, if $(n,k)$ is the $i$th pair, then $$n(n-1)/2+1\leq i\leq n(n+1)/2.$$

So we want to find the largest $n$ such that $n(n-1)<2i$ or $(2n-1)^2<8i+1$ or $2n-1=\sqrt{8i+1}$ or $n<\frac{\sqrt{8i+1}+1}2.$

So we get $n=\left\lceil\frac{\sqrt{8i+1}+1}2\right\rceil-1.$

You get $k=i-\frac{n(n-1)}2-1.$

You can write these in closed form, but it will be ugly, something like:

$$2^{\left\lceil(\sqrt{8i+1}+1)/2\right\rceil-1}+2^{i-...}$$

Where the omitted part is $n(n-1)/2$ where $n$ is that nasty expression.

It's not pretty.

If you write $f(i)=\lceil (\sqrt{8i+1}+1)/2\rceil-1,$ you can write it as:

$$g(i)=2^{f(i)}+2^{i-1-f(i)(f(i)-1)/2}$$

So when $i=8,$ $n=f(i)= 4,$ and $k=7-4\cdot3/2=1,$ so we get: $2^4+2^1.$

Answer 2

Highjacking the comment of lulu:

In the interval $~[~2^{k-1} + 1, ~2^k],~$ there are exactly $~(k-1)~$ numbers which will each have exactly $~2~$ 1's in their binary representation.

For example, in the interval $~[2^3 + 1, ~2^4] = [9,16],~$ you have the three numbers
$~9 = 1001_2, ~10 = 1010_2, ~$ and $~12 = 1100_2.~$

---

For $~r \in \Bbb{Z_{\geq 2}}, ~$ let $~f(r)~$ denote $~\displaystyle \sum_{k=2}^{r} (k-1).~$

This implies that :

• $\displaystyle f(r) = \sum_{k=2}^r (k-1) = \sum_{k=1}^{r-1} k = \frac{(r-1)r}{2}.$

• The number of positive integers in the interval $~[1,2^r]~$ that have a base-2 representation which contains exactly two 1's is $~f(r).$

So, to find the $~n$-th positive integer that has exactly two 1's in its base-2 representation:

Let $~R~$ denote the largest positive integer such that $f(R) < n.$

This implies that $~f(R) < n \leq f(R+1).$

Now, consider the sequence of numbers in the interval $~[2^{R} + 1, 2^{R+1}],~$ expressed in binary.

Of these $~2^{R}~$ numbers, the $~(R)~$ numbers that have exactly two 1's in their binary representation, may be expressed, in ascending order as

• $1000\cdots 0001.$

• $1000\cdots 0010.$

• $1000\cdots 0100.$

• $1000\cdots 1000.$

• $\cdots$

• $1001\cdots 0000.$

• $1010\cdots 0000.$

• $1100\cdots 0000.$

So, when $f(R) < n \leq f(R+1),~$ then you let $~E = n - f(R),~$ and take the $~E$-th number from the above sequence.