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