Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Number of powers of two needed to be added to the given powers of two to write the (sum of given powers and added powers of two)number of the form $2^k-1$ where $k$ is any integer.

Okay, let me explain the question.

Suppose you are given: $2^0 , 2^1 , 2^2$

Here sum of the numbers $=1+2+4=7=2^3-1$. So, there is no need to add any powers of two :)

Suppose you are given: $2^2 , 2^4 , 2^5$

Here sum of the numbers $=4+16+32=52$ which cannot be written as $2^k-1$ for any $k$.

So, we are adding here $2^0,2^1,2^3$ to the above sum which makes it $63 = 2^6 -1$.

Answer here is $3$ because we are adding here three powers of two ($2^0,2^1,2^3$).

I know that any number can be represented as sum of powers of two. But,can somebody give me an insight how to derive solution for this problem?

Thank you!

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Suppose that you’re given $2^{a_1},2^{a_2},\ldots,2^{a_n}$, where $a_1\le a_2\le\ldots\le a_n$. If $a_1=a_2$, erase $2^{a_1}$ and $2^{a_2}$ and write down $2^{a_1+1}$; then sort the powers of $2$ into non-decreasing order again. Repeat until the two smallest powers are different. Then do the same thing with the second-smallest power, and so on up the line.

Example: You’re given $2^2,2^2,2^2,2^2,2^3,2^4,2^7$. The stages are shown below: $$\begin{align*}&\color{brown}{2^2,2^2},2^2,2^2,2^3,2^4,2^7\\&\color{brown}{2^3},2^2,2^2,2^3,2^4,2^7\\&2^2,2^2,2^3,2^3,2^4,2^7\\&\color{brown}{2^2,2^2},2^3,2^3,2^4,2^7\\&\color{brown}{2^3},2^3,2^3,2^4,2^7\\&2^3,2^3,2^3,2^4,2^7\\&\color{brown}{2^4},2^3,2^4,2^7\\&2^3,2^4,2^4,2^7\\&2^3,\color{brown}{2^4,2^4,}2^7\\&2^3,\color{brown}{2^5},2^7\\&2^4,2^5,2^7\end{align*}$$

When the process is complete, you’ll have at most one copy of each power of $2$. Now fill in all missing powers below the largest; in the example that means adding $2^0,2^1,2^2,2^3$, and $2^6$. If the highest power that you have after the consolidation step is $2^a$, the sum will be $2^{a+1}-1$.

share|improve this answer
    
Beautiful pattern :D Thanks for the answer sir :) –  vaidy_mit Oct 27 '13 at 13:32
    
@vaidy_mit: You’re welcome. –  Brian M. Scott Oct 27 '13 at 14:23

Hint: what is $2^0 + 2^1 + \ldots + 2^{k-1}$?

share|improve this answer
    
So,finding the missing numbers between 0 to k-1 will give the solution ? Sir,can you please give me another hint ! –  vaidy_mit Oct 27 '13 at 7:36
    
That's right. You need to put in the missing numbers. –  Robert Israel Oct 27 '13 at 8:03
    
Sir,but what if,if we are given 2^2,2^2,2^2,2^2 ?? –  vaidy_mit Oct 27 '13 at 8:32
    
Those 4 numbers sum to $2^4$, so by what you've seen here, you need to put in $2^0$, $2^1$, $2^2$, and $2^3$. –  Gerry Myerson Oct 27 '13 at 9:42
1  
The algorithmic approach is, add up the numbers you're given, write that sum out in binary, then you can see where the gaps are in the powers of 2. –  Gerry Myerson Oct 27 '13 at 11:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.