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{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}

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

  • 1
    $\begingroup$ 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. $\endgroup$ – ms08030 Aug 24 '18 at 18:31
  • $\begingroup$ @ms08030 Thank you for your comment. Could you please write down the full answer? $\endgroup$ – Chris Aug 24 '18 at 20:55
  • $\begingroup$ @Chris You can't claim the $3^{rd}$ claim. $l(a)=l(b)$ does not implies $a=b$. $\endgroup$ – tarit goswami Aug 24 '18 at 21:12
  • 1
    $\begingroup$ @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? $\endgroup$ – Chris Aug 24 '18 at 21:17
  • 1
    $\begingroup$ Yeah, correct .. $\endgroup$ – tarit goswami Aug 24 '18 at 21:20

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.


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.