# Questions on the length of a positive integer $a\in \mathbb{Z}^+$.

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.

1. $\ell (a)=k\iff 2^{k-1}\leq a<2^k$.
2. We suppose that $a,b\in \mathbb{Z}^+$. Then, $a\leq b \implies \ell(a) \leq \ell(b)$. Is the inverse $\Longleftarrow"$ direction true?
3. Also, can we claim that $a=b\iff \ell(a)=\ell(b) ?$

My attempt. 1. We have that $$\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}$$

1. We suppose that $a \leq b$. If $\ell(a)>\ell(b)$ then:

$$\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}$$

Are these proofs correct? Are there other ways to prove these properties (especially the second) ?

• Your proof of 1 is correct, and the rest follows from there. Try to see that opposite implication is not true for 2. 1 should also tell you that 3 does not hold. – ms08030 Aug 24 '18 at 18:31
• @ms08030 Thank you for your comment. Could you please write down the full answer? – Chris Aug 24 '18 at 20:55
• @Chris You can't claim the $3^{rd}$ claim. $l(a)=l(b)$ does not implies $a=b$. – tarit goswami Aug 24 '18 at 21:12
• @taritgoswami Thank you for your comment. A very simply thought is the following. If we take $a:=(1010)_2$ and $b:=(1111)_2$, then $a\neq b$, but $\ell (a) = \ell (b)$. Also, if $a=(a_1 \cdots a_k)=b=(b_1\cdots b_k)$ then $\ell(a)=\ell(b)=k$. Right? – Chris Aug 24 '18 at 21:17
• Yeah, correct .. – tarit goswami Aug 24 '18 at 21:20

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.