Trouble with a proposition

Proposition 5.18 (An introduction to mathematical cryptography)

Let n be a positive integer and let $\displaystyle k=\lfloor \log n \rfloor +1 .$ which means that $\displaystyle 2^k > n.$ Then we can always write $\displaystyle n = u_0 + u_1*2+u_2*4+u_3*8+...+u_k*2^k$

With $\displaystyle u_0,u_1,...,u_k \in \textbracerleft -1,0,1 \textbracerright $ and at most $\displaystyle \frac{1}{2}k$ of the $\displaystyle u_i$ nonzero.

So say if we have n=61 then $\displaystyle \lfloor log n \rfloor + 1 = 5 $ then $\displaystyle 2^5 = 32$ which is definitly not greater than 61. So the first line of the proposition is not correct. Where on earth am i going wrong!! I must be missing something?

Any insight would be greatly appreciated,

cheers

Re: Trouble with a proposition

Quote:

Originally Posted by

**liedora** Proposition 5.18 (An introduction to mathematical cryptography)

Let n be a positive integer and let $\displaystyle k=\lfloor \log n \rfloor +1 .$ which means that $\displaystyle 2^k > n.$ Then we can always write $\displaystyle n = u_0 + u_1*2+u_2*4+u_3*8+...+u_k*2^k$

With $\displaystyle u_0,u_1,...,u_k \in \{ -1,0,1 \} $ and at most $\displaystyle \tfrac{1}{2}k$ of the $\displaystyle u_i$ nonzero.

So say if we have n=61 then $\displaystyle \lfloor \log n \rfloor + 1 = 5 $

In fact, the log (to base 2) of 61 is 5.93..., so its integer part is 5, and $\displaystyle \color{red}k=\lfloor \log n \rfloor +1=5+1=6$, not 5.

then $\displaystyle 2^5 = 32$ which is definitely not greater than 61. So the first line of the proposition is not correct. Where on earth am i going wrong!! I must be missing something?

It doesn't explicitly say so, but the context makes it clear that the logs here must be to base 2.

..