A set of integers Assume that there is a set of ordered integers initially containing number $1$ to a given $n$. At each step, the lowest number in the set is removed, if the number was odd, then we go to the next step and if it was even, half of that number is inserted into the set and the cycle repeats until the set is empty.
My question is, how many steps does it take for a given number $n$ to finish the whole set?
I think it should be something the form of $2k - x$ where $x$ itself is likely a complex expression but I just can't seem to figure it out. Any help would be appreciated. (I got that from trial and error, by the way, no logic or proof behind it, I know that the answer is $\lfloor \frac{n}{2} \rfloor$+"The number of times each even number can be divided by 2", but I just can't find a closed formula)

Let $s(n)$ be the number steps required.
Each number $k$ is acted on $1+\nu_2(k)$ times before being discarded completely, where $\nu_2(k)$ is the highest power of $2$ that divides $k$. For example, $\nu_2(24) =3 $ because $2^3$ divides $24$ but $2^4$ does not.
So $s(n) = \sum_1^n \left(1+\nu_2(i)\right) = n+\sum_1^n\nu_2(i)$
Now $\sum_1^n\nu_2(i)$ is the count of even numbers up to $n$, plus the count of numbers divisible by $4$, plus the count of numbers divisible by $8$, etc. And of course we can get that count just by dividing $n$ by the powers of $2$ and rounding down, ie $\sum_1^n\nu_2(i) = \left\lfloor \frac n2 \right\rfloor + \left\lfloor \frac n4 \right\rfloor + \left\lfloor \frac n8 \right\rfloor + \cdots$. 
Where $n=2^k$, this is actually equal to $n{-}1$, and for $n=2^k-1$ of course it is $n{-}k$. So $s(n) = 2n-e$, where $e$ depends on where the number sits between powers of $2$. 
A little lateral thinking uncovers that $e$ is actually the digit sum of $n$ in binary.
