# Algorithm / equation to determine parts of a sum based on restrictions

I am having trouble in identifying the equations or algorithm for parts of a sum on a problem I am working on. I clearly see a pattern just having a tough time creating an equation behind it. Here is the problem. I have 7 unique numbers in which I can use. A = 1 B = 2 C = 4 D = 8 E = 16 F = 32 G = 64

I have manually found every combo using these numbers to find the sum please see picture of excel for an example of first 30 combos. I am trying to for each (A, B, C etc.)an equation based on the number 1 to 127 to identify whether we include A, B, C etc.

so for example: A = 1, so if the sum = 1 we have , if sum is 2 we have B we cannot use A, B, C for each sum more then once and if the sum is one of the 7 we ignore any other possibility. Please let me know if anyone is able to help me with this problem.

Manually compiled all possibilities

• This might be relevant. Dec 30, 2015 at 4:46

Manually constructing the components of the sums is a good start. Do you see any immediate patterns in the image?

One thing to notice is that there is a special property that each $A, B, ..., G$ have in common. Namely, they are all powers of two ($A = 2^0$, $B = 2^1$, $C = 2^2$, etc.). A good place to being would be to look at where $A$ is used. Looking at your image, you should see that $A$ appears to be used in every other sum.

$1 = A$

$3 = A + B$

$5 = A + C$

$7 = A + B + C$

and so on. When we think about why that might be, we see that $A$ is the only odd number - every other number is even. Therefore, to get an odd number as a sum, we must include $A$ (can you explain why?). That gives us a quick and easy way to deal with whether or not $A$ is used (is the number odd?)

Well, what about the others? There are multiple ways to go about extending that result. The way that is most intuitive for me is as follows. Let's say we're concerned about the number $n$ which lies between 1 and 127 inclusive. We want to know how to write $n_1$ as a sum of $A$ through $G$. The first thing I'm going to do is find the biggest number that can be included in the sum. This can be done by checking if $G > n_1$, and if it's not then check if $F > n_1$, etc. The first number that is not greater than $n_1$, i.e. less than or equal to $n_1$ is the biggest number that can possibly be included in the sum. Let's just say, for example, that $D$ is the largest number that be included in the sum. Now I'm going to set $n_2 = n_1 - D$. Then I'm going to start over again with $n_2$ instead of $n_1$. We can make a quick short-cut by realizing that we don't need to check that $G > n_2$, $F > n_2$, etc. down through $D > n_2$ since we already know those were greater than $n_1$, and we also know that $n_1 > n_2$.

We keep repeating this process until we reach 0, and each number we included along the way is used in the final sum.

An example:

$n_1 = 121$

$n_2 = 121 - G = 121 - 64 = 57$

$n_3 = n_2 - F = 57 - 32 = 25$

$n_4 = n_3 - E = 25 - 16 = 9$

$n_5 = n_4 - C = 9 - 8 = 1$

$n_6 = n_5 - A = 1 - 1 = 0$

Thus the numbers we include are $A, C, E, F, G$, or in other words, $n_1 = A + C + E + F + G$.

As far as proving why this is correct, we should notice that $A < B$, $A + B < C$, $A + B + C < D$, and etc. Can you see why this is useful?