# Give an expression to the decimal number given after manipulations

Given a natural number in decimal presentation $$N$$.

Give an expression (depending on $$N$$ and/or $$k$$) to the decimal (representation at base $$10$$) number given after the manipulations below:

$$\text{(a)}:$$ Converting $$N$$ to binary representation, and adding $$k$$ times $$1$$ from the right.

$$\text{(b)}:$$ Converting $$N$$ to binary representation, and adding $$1$$ from the left.

$$\text{(c)}:$$ Converting $$N$$ to binary representation, and adding $$k$$ times $$1$$ from the left.

My try:

$$\text{(a)}:$$ $$N + \sum _{i=1}^k\:2(k + \lfloor \log_2N+1 \rfloor)$$

$$\text{(b)}:$$ $$N + 2^{\lfloor \log_2N+1 \rfloor}$$

$$\text{(c)}:$$ $$N + \sum _{i=1}^k\:2^{k \lfloor \log_2N+1 \rfloor}$$

Please let me know if it's true.

• I'm not sure I follow. Suppose $N=1$ and $k=2$. What are the results you have in mind? – lulu Apr 9 '17 at 15:29
• @lulu $\text{(a)}: 7, \text{(b)}: 3, \text{(c)}: 7$ – Itay4 Apr 9 '17 at 15:32
• So you want to convert back to base $10$ at the end? You didn't say that. Do your formulas yield those three numbers? – lulu Apr 9 '17 at 15:33
• @lulu I wrote "give an expression to the decimal number given after the manipulations". I'm struggling with $\text{a}$, I'm pretty sure the other two are correct. – Itay4 Apr 9 '17 at 15:35
• I'm telling you your question isn't clear, it's easy to edit it for clarity. As you say, $a$ is certainly wrong. $b$ is correct for this example but if I take $N=3,k=2$ I believe I get $3\to 11\to 1111\to 15$, no? But your formula would seem to give $3+2^{\lfloor 1.585+1\rfloor}=3+2^2=7$. Or have I misunderstood something? – lulu Apr 9 '17 at 15:40

Let $B_k$ denote the binary block $$B_k= \underbrace {11\cdots 11}_k$$ We remark that, in base $10$, $B_k=2^k-1$.
For $a$: we need to create $k$ zeroes on the right of the binary expression for $N$. We do this by multiplying by $2^k$. Then we add $B_k$. Thus we want $$N\mapsto 2^kN+2^k-1$$
Example: $N=5,k=2$. Then our operation yields $$5\to 101\to 10111\to 23$$ our formula yields $$4\times 5+4-1=23$$ as desired.
$b$ is correct as it stands.
For $c$: we need to put the block $B_k$ on the left so we have to multiply by it by $2^{L(N)}$ where $L(N)$ denotes the length of the binary expression for $N$. Of course $L(N)=\lfloor \log_2N+1\rfloor$ so the operation we want is $$N\mapsto N+2^{\lfloor \log_2N+1\rfloor}\times \left(2^k-1\right)$$
Example: As before, take $N=5,k=2$. Now our operation yields $$5\to 101\to 11101\to 29$$ We remark that $\log_25 \approx 2.322$ so $L(5)=3$ (as it should) so our formula yields $$5+2^3\times 3=5+24=29$$ as desired