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.

  • $\begingroup$ I'm not sure I follow. Suppose $N=1$ and $k=2$. What are the results you have in mind? $\endgroup$ – lulu Apr 9 '17 at 15:29
  • $\begingroup$ @lulu $\text{(a)}: 7, \text{(b)}: 3, \text{(c)}: 7$ $\endgroup$ – Itay4 Apr 9 '17 at 15:32
  • $\begingroup$ So you want to convert back to base $10$ at the end? You didn't say that. Do your formulas yield those three numbers? $\endgroup$ – lulu Apr 9 '17 at 15:33
  • $\begingroup$ @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. $\endgroup$ – Itay4 Apr 9 '17 at 15:35
  • $\begingroup$ 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? $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.