1

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.

Joao
  • 1,390
ADGB
  • 140

2 Answers2

2

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

Empy2
  • 50,853
1

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

Did
  • 279,727
  • Hi Did, thank you for your answer. Unfortunately, I am not as advanced in math as you. I am building a computer algorithm that will give me these numbers to then use them in a Cellular automaton model for a school project. Michael's answer is very easy to understand and apply as a python procedure. However, it seems that your solution could lead to a very efficient piece of code. Would you care to develop more for someone with average math understanding? – ADGB May 03 '14 at 07:20
  • I thought it was already written in a quite algorithmic way. Which step is unclear to you? – Did May 03 '14 at 07:22
  • So, you'll correct me if I'm wrong but I understand that to identify every number that will comply with the set condition: 1. when the set = 0 then it is an empty set. 2. On the second point is where I am not understanding everything specifically: "such that 2i(n)⩽n<2i(n)+1, namely, i(n)=⌊log2n⌋, then K(n)={i(n)}∪K(n−2i(n)) and K(n−2i(n))⊆{0,1,…,i(n)−1}". Thank you. – ADGB May 03 '14 at 07:42
  • See Example. $ $ – Did May 03 '14 at 08:07