3
$\begingroup$

We can add do the following operations

a) add 1 to number

b) multiply number by 2

By using only a) and b) operations we can get any number from 0.

How much operations we need to do at least to get N?

  • 1
    Write $N$ in binary.2012-12-28

2 Answers 2

5

Write $N\ge0$ in binary. Let $d_0(N)$ be the number of zeroes and $d_1(N)$ be the number of ones.

Claim: The minimal number of steps is $s(N):=d_0(N)+2d_1(N)-1$.

Proof: This is true for $N=0$, where $d_1(N)=0$, $d_0(N)=1$ and we need $0$ steps.

If $N=2k+1$ is odd, the last step must be addition of one. Hence to produce $N$ we must first produce $2k$, then add one. Note that $d_0(N)=d_0(2k)-1$, $d_1(N)=d_1(2k)+1$ and hence $s(N)=s(2k)+1$. Since $s(2k)$ is the minmal number of steps to produce $2k$, we conclude that $s(N)$ is the number of steps needed for $N$.

If $N\ge 2$ is even, we have two options: Produce $N-1$ and add one. Or produce $\frac N2$ and double. For the second method, we observe that $d_1(N)=d_1(\frac N2)$ and $d_0(N)=d_0(\frac N2)+1$ (this requires $N\ge2$), hence $s(N)=s(\frac N2)+1$. Thus we need to show that the path via $N-1$ cannot be better. If $N=2^r$ is a power of $2$ with $r\ge1$, note that $d_0(N)=r$, $d_1(N)=1$, $d_0(N-1)=0$, $d_1(N-1)=r$, hence $s(N)=r+1$, $s(N-1)=2r-1$. Thus $s(N)=s(N-1)+1$ if $r=1$ (i.e. we have a free choice to double or add in order to obtain $2$ from $1$), whereas $s(N) for $r>1$ (i.e. the straightforward method via $\frac N2$ is strictly faster than the method via $N-1$). If $N=2^ru$ with $r\ge 1$ and $u>1$ odd, we have $d_0(N)=d_0(N-1)+r-1$, $d_1(N)=d_1(N-1)-r+1$, hence $s(N)=s(N-1)-r+1\le s(N-1)$. Therefore $s(N-1)+1>s(N)$, i.e. the method via $N-1$ is strictly slower than the method via $\frac N2$. $_\square$

  • 0
    +1 Hagen: It seems people are being a bit stingy with upvotes today! So I'm making a point of voting on (what I take to be) the best answers!2012-12-28
0

Think binary. If you write $N$ in binary notation, then multiplying by 2 simply shifts digits one space to the left and appends zero on the right. Thus, in at most two operations per binary digit of $N$, and working from the leftmost digits to the right, we could get from $0$ to $N$. That's at most $2 \lfloor \log_2 N \rfloor$ operations.

Here's an illustration with $N = 29$. In binary, $N = 11101$.

$\begin{array}{ll} \textrm{start} & 0 \\ (+1) & 1 \\ (\times 2) & 10 \\ (+1) & 11 \\ (\times 2) & 110 \\ (+1) & 111 \\ (\times 2) & 1110 \\ (\times 2) & 11100 \\ (+1) & 11101 \\ \end{array}$

  • 0
    but how to prove that it is optimal solution ?2012-12-28