Let's say we have a set of natural numbers $ S=\{2^a, 2^b, 2^c, 2^d, ...\} $ and we have $z$ where $ z=\sum_{i=0}^n S_i $ How can we find the set from $z$ ?
For example, let $z = 83$ Then the set $S$ = $\{2^0, 2^1, 2^4, 2^6\} as 1 + 2 + 16 + 64 = 83$
What is the formula that can solve this problem? input: $c$ output $S$
On
This statement is precisely that every natural number has a unique/distinct binary representation.
There's no "formula" but there is an iterative algorithm.
Start with $n$. And start with $flag = 0$
Check and see if $n$ is odd or even.
If $n$ is odd then $2^{flag} = 2^0$ is in the set. If so subtract $1$.
If divide the result and repeat for $flag = 1$.
If the result is odd then $2^{flag} = 2^1$ is in the set. If so subtract $1$.
Example $83$ is odd.
$2^0$ is in the list. Subtract 1 to get $82$.
Divide by $2$ to get $41$.
$41$ is odd.
$2^1$ is in the list. Subtract 1 to get $40$.
Divide by $2$ to get $20$.
$20$ is even.
$2^2$ is not on the list.
Divede by $2$ to get $10$.
$10$ is even.
$2^3$ is not on the list.
Divide by $2$ to get $5$.
$5$ is odd.
$2^4$ is on the list. Subtract $1$ to get $4$.
Divide by $2$ to get $2$.
$2$ is if even.
$2^5$ is not on the list.
Divide by $2$ to get $1$.
$1$ is odd.
$2^6$ is on the list. Subtract $1$ to get $0$.
We are done.
The list is $\{2^0,2^1, 2^4, 2^6\}$ and $2^6 + 2^4 + 2^1 + 2^0 = 64 + 0*32 + 16 +0*8 + 0*4 + 2 + 1 = 1010011_2 = 83$.
On
Notice that you can get that by "2 divides into 83 41 times with remainder 1" so the lowest binary digit (bit) is 1. "2 divides into 41 20 times with remainder 1" so the next bit is also 1. "2 divides into 20 10 times with remainder 0" so the next bit is 0. "2 divides into 10 5 times with remainder 0" so the next bit is 0. "2 divides into 5 twice with remainder 1" so the next bit is 1, "2 divides into 2 once with remainder 0". Finally, "2 divides into 1 0 times with remainder 1" so the leading bit is 1.
As Andronicus said, 83, in binary, is $1010011_b = 1(2^6)+ 0(2^5)+ 1(2^4)+ 0(2^3)+ 0(2^2)+ 1(2^1)+ 1(2^0)= 1(64)+ 0(32)+ 1(16)+ 0(8)+ 0(4)+ 1(2)+ 1(1)= 64+ 16+ 2+ 1 = 83.$
Another example: 395. 395 divided by 2 is 197 with remainder 1. 197 divided by 2 is 98 with remainder 1. 98 divided by 2 is 49 with remainder 0. 49 divided by 2 is 24 with remainder 1. 24 divided by 2 is 12 with remainder 0. 12 divided by 2 is 6 with remainder 0. 6 divided by 2 is 3 with remainder 0. 3 divided by 2 is 1 with remainder 1. 1 divided by 2 is 0 with remainder 1. Collecting the remainders, $395= 1(2^8)+ 1(2^7)+ 0(2^6)+ 0(2^5)+ 0(2^4)+ 1(2^3)+ 0(2^2)+ 1(2^1)+ 1(2^0)= 256+ 128+ 8+ 4+ 2+ 1$. In binary that is $110001011_b$.
On
The key is that $1 + 2 + 4 + 8 + \dots + 2^{n-1} < 2^{n}$. So what ever the largest $2^n$ you can find with $2^n < z$, that has to be in the sum because the remaining $1 + \dots + 2^{n - 1}$ can't contribute to the sum as much as $2^n$.
So for $z = 83$, the largest $2^n$ is $2^8=64$. So $64$ has to be in the set.
After that just subtract and repeat. Your new $z$ would be $83 - 64 = 19$, so repeat the problem with $z = 19$. (The largest $2^n$ you'll find there will be $2^4 = 16)$.
You can write $z$ in binary, so that you can see, at what places in geometrical sequence $a_n 2^n$ is $a_n$ non-zero. For example: $83 = 1010011_b$. One can see now, that $83 = 2^6 + 2^4 + 2^1 + 2^0$.