# Thread: Breaking a stick of lenght of power of 2

1. ## Breaking a stick of lenght of power of 2

hi, if there is a stick of lenght which of the form of power of 2 , then what is the minimum number of times one must break the stick to get a lenght , if the stick can only be broken into half each time.
E.g if the stick is of lenght 8, then to get a length of 5 we must break it a minimum 3 times .
Is there any general formula to it ?
Thanks.

2. Oh this is so my thing, for I, in the least, "like" (i.e. LOVE) the binary system.
Anyway, consider 5 in the binary system - 5=101. Note that it's last digit is one. That also means that the highest power of 2 that divides it is 1 (i.e. 2 to 0).
Now let's take another number e.g. 44.
It can be written as 44=32+8+4=101100. Note the two zeroes from the right. It is the same as saying that the number is divisible by 4 (i.e. the second power of 2).
So if understood you correctly, the problem you posed for n=44, would be something like this:
(64)=(32,32)=(32,16,16)=(32,16,8,8)=(32,16,8,4,4) - 4 breakings
And now you can construct 44 from these numbers...
So if got it right your solution in a generic formula would be:
$\displaystyle x=\lceil \log_{2} n \rceil-d$, where d is the power of the highest divisor of the number n.
So I guess that's it?

EDIT: Ah, I made a mistake by claiming you could write 44 with (32,16,8,8)... upon better inspection, I see the formula uses the ceil function rather than the floor but now I'm positive that it's correct.