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.
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