Vtyjkyuk

Lets say there is positive number $n = 118$, which we want to represent as sum of powers of i.e. $2^k$ (while $n$ being always $>= 0$).

Following the repetitive division by powers of 2, we obtain that $n$ can be written as the sum of following powers of $2$:

$118$ = $2^6$ + $2^5$ + $2^4$ + $2^2$ + $2^1$

On the other hand, the solution $(sum_i=0^6 2^i = 127)$ is greater than $118$. My question is: how can we generalize this descending pattern of powers, through which we will know that we have to exclude $2^3$ and $2^0$ from the sum? Thanks.

Well, I can think of $2$ ways to do that:

1) We can represent the number in base $2$. When we do that, whenever we have a $0$ in base $2$ representation, corresponding power should be excluded.

For example, $118 = (1110110)_2$ so we should exclude $2^0$ and $2^3$.

2) This one is more like an algorithm. Let our number be $n$. Then, first we find smallest number $k$ such that $2^k - 1 ge n$. Then we find the difference $d = (2^k - 1) - n$ and express it by using powers of $2$. While doing this, we should find largest $m$ such that $2^m <= d$. Then do the same for $d - 2^m$ and continue this until $d = 0$. The $m$ values you find during this process will be the excluded powers.

For example, we have $n = 118$. Smallest number $k$ such that $2^k - 1 > n$ is $k = 7$ so we have $d = 9$. Then the largest $m$ such that $2^m le d$ is $m = 3$. So our new $d$ is $9-2^3 = 1$. Then the largest $m$ such that $2^m le d$ is $m = 0$ and our new difference is $0$ so we are done by excluding $2^3$ and $2^0$.