Generating numbers We can do the following actions: add $1$ or multiply by $2$. Find the minimum number of operations to get an arbitrary natural number $N$ from $0$ using these two actions.
If we denote the minimum number with $k(n)$ then it is obvious that $k(n) \leq N$. If $N$ is a power of two, $k(n)=\log_2N+1$. Please help to discuss the problem wholly.
 A: Hint:  Think backwards. What's the quickest way to get from $N$ to $0$ if all you can do is subtract $1$ or divide by $2$?
A: My candidate for $k$ would be this function
$$
k(N) = 
\begin{cases}
0 & ; N = 0 \\
1 + k(N-1) &; N \bmod 2 = 1 \\
1 + k(N/2) & ; N \bmod 2 = 0, N > 0
\end{cases}
$$
The first clause is needed to terminate a recursion.
For $N > 0$, each integer is either odd or even.
As $2k$ is even for any positive integer $k$, an odd number $N$ must have been reached by an addition of one, this is the second clause.
An positive even number $N$ might have been reached either bei addition from $N-1$ or by multiplication from $N/2$.
However $N-1 = N/2$ for $N=2$ and $N-1 > N/2$ for $N > 2$. So to choose the multiplication is as good or better than choosing the addition. This is the reason for the third clause.
Now assume you have $w = (N)_2$, $N$ given as word in base $2$, thus a binary word, using the usual normalization of removing leading $0$ digits.
Now evaluating the above $k$ function is easy: If $w = 0$ then $N=0$ and $k(0)=0$. Otherwise $N > 0$.
If $w = u0$, for some prefix word $u$, then $N$ is even and the third clause applies, we have $k(u0) = 1 + k(u)$.
If $w = u1$  then $N$ is odd and we evaluate the second clause. We get $k(u1) = 1 + k(u0)$. Which then leads to the first clause ($u = \epsilon$) and $k(1)= 1$  or to the third clause, $k(u1) = 1 + k(u0) = 2 + k(u)$.
Combining these gives
$$
k(w) = 
\#_0(w) + 2 \#_1(w) - 1 = \lvert w \rvert + \#_1(w) - 1 \quad (w \ne \epsilon)
$$
where $\lvert w\rvert$ is the length of the word $w$ and $\#_d(w)$ is the number of $d$ symbols in $w$.
