$n$ = sum of numbers in progression $2^n$

Question

I have looked everywhere and cannot find an answer. If the answer already exists, please refer me to it.

I have a number $n$ and need to know the formula to find the numbers in the series $2^n$ that when summed equal $n$.

For example:

$25 = 16 + 8 + 1$ or $25 = 2^4 + 2^3 + 2^0$

Thank you.

Answer 1

You want to write the number as binary.

To do that, divide the number by 2 over and over again, and write down the remainders. for example,

$\begin{eqnarray} 25/2 = 12, remainder &1\\ 12/2 = 6, remainder & 0\\ 6/2 = 3, remainder &0\\ 3/2 = 1, remainder &1\\ 1/2 = 0, remainder &1\end{eqnarray}$

Now, each time the remainder is 1, you get a power of 2. Start with $2^0=1$ at the top, and count down. The remainder is 1 three times, so the powers of 2 are $2^0$, not $2^1$, not $2^2$, then $2^3$, and $2^4$.

So 25 = $2^0+2^3+2^4$.

Answer 2

You seem to look for a way to deduce the set $K(n)$ from the nonnegative integer $n$, where the set $K(n)$ is uniquely defined by the condition that $$n=\sum\limits_{k\in K(n)}2^k.$$ Then a recursive identification of $K(n)$ is as follows:

• $K(0)=\varnothing$.
• If $n\geqslant1$, there exists a unique $i(n)\geqslant0$ such that $2^{i(n)}\leqslant n\lt2^{i(n)+1}$, namely, $i(n)=\lfloor\log_2n\rfloor$, then $K(n)=\{i(n)\}\cup K(n-2^{i(n)})$ and $K(n-2^{i(n)})\subseteq\{0,1,\ldots,i(n)-1\}$.

Example: If $n=87$ then $2^6=64$ hence $2^6\leqslant 87\lt2^7$ and $87=2^6+23$, which implies that $K(87)=\{6\}\cup K(23)$.

Now, $2^4=16$ hence $2^4\leqslant23\lt2^5$ and $23=2^4+7$, which implies that $K(23)=\{4\}\cup K(7)$.

At this point, one knows that $K(87)=\{6,4\}\cup K(7)$ and one is left with the task of identifying $K(7)$. Since $7=2^2+2^1+2^0$, it turns out that $K(7)=\{0,1,2\}$, hence all this yields finally $$K(87)=\{0,1,2,4,6\}.$$