Trouble with a proposition

**liedora** · July 9th 2011, 08:18 PM

Proposition 5.18 (An introduction to mathematical cryptography)
Let n be a positive integer and let $k=\lfloor \log n \rfloor +1 .$ which means that $2^k > n.$ Then we can always write $n = u_0 + u_1*2+u_2*4+u_3*8+...+u_k*2^k$
With $u_0,u_1,...,u_k \in \textbracerleft -1,0,1 \textbracerright$ and at most $\frac{1}{2}k$ of the $u_i$ nonzero.

So say if we have n=61 then $\lfloor log n \rfloor + 1 = 5$ then $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

**Opalg** · July 10th 2011, 12:18 AM

Originally Posted by liedora

Proposition 5.18 (An introduction to mathematical cryptography)
Let n be a positive integer and let $k=\lfloor \log n \rfloor +1 .$ which means that $2^k > n.$ Then we can always write $n = u_0 + u_1*2+u_2*4+u_3*8+...+u_k*2^k$
With $u_0,u_1,...,u_k \in \{ -1,0,1 \}$ and at most $\tfrac{1}{2}k$ of the $u_i$ nonzero.

So say if we have n=61 then $\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 $\color{red}k=\lfloor \log n \rfloor +1=5+1=6$ , not 5.

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

Thread: Trouble with a proposition

LinkBack

Thread Tools

Display

Trouble with a proposition

Re: Trouble with a proposition

Similar Math Help Forum Discussions

Another fibonacci proposition

proof this proposition

Proposition Help!?

Proposition induction

Prove a Proposition

Search Tags