Definition. We call length of a positive integer $a\in \mathbb{Z}^+$, and we write $\ell(a)$, the number of $2$-adic digits of $a$. That is $\ell(a):=\lfloor \log _2 a\rfloor +1$.
I found on my textbook the following properties but without proof. So, I tried to prove the myself.
- $\ell (a)=k\iff 2^{k-1}\leq a<2^k$.
- We suppose that $a,b\in \mathbb{Z}^+$. Then, $a\leq b \implies \ell(a) \leq \ell(b)$. Is the inverse $``\Longleftarrow"$ direction true?
- Also, can we claim that $a=b\iff \ell(a)=\ell(b) ?$
My attempt. 1. We have that \begin{equation} \begin{split} 2^{k-1}\leq a<2^k & \iff k-1 \leq \log_2 a <k \\ &\iff \lfloor \log _2 a\rfloor =k-1 \\ & \iff k=\lfloor \log _2 a\rfloor +1=\ell(a). \end{split} \end{equation}
- We suppose that $a \leq b$. If $\ell(a)>\ell(b)$ then:
\begin{equation} \begin{split} \ell(a)>\ell(b) & \iff \lfloor \log_2 a \rfloor +1 > \log_2 b \rfloor +1\\ & \iff \lfloor \log_2 a \rfloor > \log_2 b \rfloor \\ & \implies \log_2 a > \log_2 b \\ & \iff a>b, \text{ contradiction. } \end{split} \end{equation}
Are these proofs correct? Are there other ways to prove these properties (especially the second) ?
Thank you in advance.
The first one is OK.
That $a \le b$ implies $\ell(a) \le \ell(b)$ follows from the facts that $\log_2$ is a non-decreasing function and $\lfloor \cdot \rfloor$ is too:
$a \le b \implies \log_2(a) \le \log_2(b) \implies \lfloor \log_2(a) \rfloor \le \lfloor \log_2(b) \rfloor \implies \ell(a) = \lfloor \log_2(a) \rfloor + 1 \le \lfloor \log_2(b) \rfloor + 1 = \ell(b)$.
But $8 = (1000)_2$ and $15=(1111)_2$ so $\ell(15) = \ell(8) = 4$ while $15 \not \le 8$. This is a counterexample both to the reverse implication of the second as to the reverse implication of the third question.
What is true though is that $\ell(a) < \ell(b)$ implies $a < b$. (i.e the equal part is the problem in this reverse implication): Suppose that $\ell(b) = k$. This implies that $2^{k-1} \le b$ while $\ell(a) < \ell(b)$ implies $\ell(a) \le k-1$ so that $a < 2^{k-1}$, hence $a < b$ then holds.