Writing a number as power of two

Question

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!

score 3 · Accepted Answer · answered Oct 27 '13 at 12:48

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

score 1 · Answer 2 · answered Oct 27 '13 at 07:26

1

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

answered Oct 27 '13 at 07:26

Robert Israel

448,999

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 07:36
That's right. You need to put in the missing numbers. – Robert Israel Oct 27 '13 at 08:03
Sir,but what if,if we are given 2^2,2^2,2^2,2^2 ?? – vaidy_mit Oct 27 '13 at 08: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 09:42
@Gerry Yeah,but how to find that ?I need an algorithmic approach sir :) – vaidy_mit Oct 27 '13 at 10:39
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

Writing a number as power of two

2 Answers2