## Equal sum of a subset and remainder of a set

Math help in Numerical Analysis, Systems of Equations: Cholesky, LU factorization, Consistence, Differential Equations (ODE), Euler's Method, Approximation of Integrals: Simpson's method, Partial Differential Equations (PDE), Symbolic Computations, Latex, Game Theory, Graph Theory; Relations, Equivalence, Implication, Boolean values, True, False, or, and, xor, Predicates, First Order Logic, Second Order Logic, Decidability, Turing machine, P problems, NP problems, Axioms, Axiom of Choice; Paradoxes: Russel, Banach-Tarski; Goedel's Incompleteness Theorem, Foundations of Mathematics on My Math Forum.
Math problems on Numerical Series Geometry Other Topics

### Re: Equal sum of a subset and remainder of a set

Hoempa wrote:You may consider the use of a list in your program. The idea is that you construct the set by using the needed sum of every subset, instead of puzzling arround. This way, it would be more of searching for the solution, rather than calculating the options. I'm not sure about the efficiency. Perhaps, you could construct all possibilities to expres the sum of a subset as a sum. e.g. 106=80+26=80+20+6... until you have terms that can be an element of your set.

The restriction on the possible values of the elements seem useful, by looking at the last digit of the sums.

The complexity is something like $\prod_{e\in E}n_e+1$ where you have $n_1$ 1s, $n_2$ 2s, ..., $n_{80}$ 80s. (I have divided by 250 here.)

This is, technically, polynomial rather than exponential, and the constants aren't too bad. In the worst case with n elements it takes time (n/16+1)^16 which is certainly doable. You could improve on that by taking some small elements and building all possible values from them, storing this in an array, then looping over all the possibilities for the others and checking if the total you get is within one of those amounts of the total. This, if I'm not mistaken, could improve complexity to $(n/16+1)^8\log n$ though (1) the constant gets worse; time probably doesn't improve much until n > 10 or n > 15; and (2) this can take a decent bit of memory if n is large.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12538
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### Re: Equal sum of a subset and remainder of a set

Maybe, it could be even more improved; Based on your idea:
CRGreathouse wrote:You could improve on that by taking some small elements and building all possible values from them, storing this in an array, then looping over all the possibilities for the others and checking if the total you get is within one of those amounts of the total.

The elements that are not divisible by 10, {1, 2, 3, 4, 5, 6, 8} determine the last digit of the sum of the subset.
I phrased this in dutch, I'll try in english.
Consider this set:
{1,1,2,4,5,5,8,10,20,30,50,80}
with a sum of 216. The sum of a subset is 216/2=108.
The sum of the digits, non-divisible by 10,
{1,1,2,4,5,5,8} is 26.
Once they are split in 2 subsets, the sums are respectively 8 in subset1 and 18 in subset2 (without loss of generality).

$8 \in subset1$ and ${1,1,2,4,5,5} \in subset2$
In subset1, 100 must be added, with these elements: {10,20,30,50,80}
80+20=100
$subset1={8, 20, 80}$ subset2={1,1,2,4,5,5,10,30,50}

By splitting in divisible and non-divisible by 10, the algorithm may be sped up; instead of 1 larger set, you can get 2 smaller sets.

I have tried some with the following, I can't make it work.

Maybe, an algorithm can be used to determine all sums that add up to for example 8.
Now, 2 can be expressed in 1 way; 1+1
3=2+1 (1 expression) but 2 can be expressed as 1+1. Therefore, 3 has 2 representations.
4=3+1=2+2 (2 expressions) 3 can be expressed in 2 sums. 2 can be expressed as 1 sum. Here comes the flaw; you can't just add these. It would yield:
4 can be expressed in 2+2+1=5 sums. But $4=3+1=2+2=2+1+1=1+1+1+1$ 4 sums.
Maybe I have an idea for that;

Determine the number of sums, we can express 8. Assume, the following are added; for example 11=1+1
11111111
We will split them with fences. For sums of 2 terms, we use 2-1=1 fence. It can be placed in 7 places.
1|1111111
11|111111
....
111111|11
1111111|1
The thing is:
2+6 is mentioned twice; as 6+2 as well. same for 5+3
7+1 is also mentioned (twice) though, 7 is not a possible value. Leaves 7C1-1-1-2=7-2-2=3 two-term sums.

Three-term sums:
1|1|111111
1|11|11111
1|111|1111
...
111111|1|1

7C2=21 options. All terms are possible values for a set. Some are counted more than once. For now, it seems like we would have to know the terms to determine how often they are counted. (1+2+5 is counted 6 times for 3!=6. 2+3+3 is counted 3 times, for 3C2=3)

Just an idea though, what do you think?
Hoempa
Super User

Posts: 1700
Joined: Thu Apr 01, 2010 9:38 am

### Re: Equal sum of a subset and remainder of a set

Hoempa wrote:Just an idea though, what do you think?

You can probably split it in four. Take the digits not divisible by 10 and split into two groups and solve for the correct last digit, giving you a table of partial solutions. Make a list of the possible tens digits from this and use those together with a third or half of the divisible-by-10 set. Find the possible values for those small multiples of ten, then loop over the possible values of the large multiples of ten until one works. If one does, find the number of tens you used from the non-multiples-of-10 and look up which one that was in your table to recover the constituents. If you never find one, it doesn't exist.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12538
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### Re: Equal sum of a subset and remainder of a set

Thanks all for all the input. I have to read it a few times and check how I could add it.

Yesterday I did some programming (not using the above input yet, just to keep it simple and get an idea of what exactly to calculate).
With my current set, some calculations could be done within 2 seconds (but that is without the sum set problem above). It was just to create all possible sets to start with. However, when I added about 10-20 values, I found out that the memory space was over 2 GB, which is more than the program can hold data (even tough I have 8GB). So I think I should go back to the original problem again and leave this 'sub'-problem of checking the sum/balancing until I have found out exactly what I need.

During the weekend I will try to write down exactly (and hopefully in somewhat formal way) what I need. However if it seems I can solve the starting problem than I really can use all the ideas.

It's just strange to find out that such a simple problem at first can get out of hand so fast. I really appreciate all your effort to help me.
michelkeijzers
Newcomer

Posts: 12
Joined: Mon Jan 31, 2011 4:50 am

### Re: Equal sum of a subset and remainder of a set

michelkeijzers wrote:Yesterday I did some programming (not using the above input yet, just to keep it simple and get an idea of what exactly to calculate).
With my current set, some calculations could be done within 2 seconds (but that is without the sum set problem above). It was just to create all possible sets to start with. However, when I added about 10-20 values, I found out that the memory space was over 2 GB, which is more than the program can hold data (even tough I have 8GB). So I think I should go back to the original problem again and leave this 'sub'-problem of checking the sum/balancing until I have found out exactly what I need.

If you treat each item separately, you need (storage per record) * 2^(# of values) storage. If 20 values takes 2 GB, that's 2000 bytes per record.

If you combine same-sized elements (so that if your first three are 250 g, you consider only four possibilities -- zero, one, two, or three used -- rather than eight) then that will take up to (storage per record) * (# of values/16 + 1)^16 storage, so the 20 values now take 860 MB instead. (Actually they'd only take <= 670 MB because of discreteness, but let's ignore that for now.)

If you store only the possibilities for half the records that's (storage per record) * (# of values/16 + 1)^8 storage instead, dropping storage needed to 1.3 MB.

The newest scheme I mentioned pushes it below that, but how much lower depends on the data. It could be nearly as good as (storage per record) * (# of values/16 + 1)^7 if your data was really cooperative, dropping the space needed below a megabyte. (The 7 comes from the number of elements divisible by 10.)

michelkeijzers wrote:During the weekend I will try to write down exactly (and hopefully in somewhat formal way) what I need. However if it seems I can solve the starting problem than I really can use all the ideas.

It's just strange to find out that such a simple problem at first can get out of hand so fast. I really appreciate all your effort to help me.

Not a problem. I'd code the answer or you but I don't know that you could afford my rates.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12538
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### Re: Equal sum of a subset and remainder of a set

CRGreathouse wrote:You can probably split it in four. Take the digits not divisible by 10 and split into two groups and solve for the correct last digit, giving you a table of partial solutions. Make a list of the possible tens digits from this and use those together with a third or half of the divisible-by-10 set. Find the possible values for those small multiples of ten, then loop over the possible values of the large multiples of ten until one works. If one does, find the number of tens you used from the non-multiples-of-10 and look up which one that was in your table to recover the constituents. If you never find one, it doesn't exist.

I'm sorry, I'm not sure if I understand you correctly, I'll show how I get it by an example.

{1,1,1,2,3,3,4,5,5,5,8,10,20,20,30,50,60,80}
sum: 308
sum of subset: 308/2=154

Split in 2; divisible and not divisible by 10.
{1,1,1,2,3,3,4,5,5,5,8} sum: 38; possible sums of subset: [4, 34]; [14, 24]
and
{10,20,20,30,50,60,80} sum: 308-38=270

From here on, I'm lost. Would you determine all posible sums for 270 from the numbers or just assume 10+260, 20+250, ... 130+140 are all possible.
We could find that, for the sum of non-divisible is 38, 110+160 is not possible for the large multiples of 10, for 160-110=50>38.
Hoempa
Super User

Posts: 1700
Joined: Thu Apr 01, 2010 9:38 am

### Re: Equal sum of a subset and remainder of a set

Hoempa wrote:Split in 2; divisible and not divisible by 10.
{1,1,1,2,3,3,4,5,5,5,8} sum: 38; possible sums of subset: [4, 34]; [14, 24]
and
{10,20,20,30,50,60,80} sum: 308-38=270

From here on, I'm lost.

You got lost before that point, I'm afraid.

You need to form the small ones into all possible groupings that would have them add up to a multiple of 10. In this case, that's
Code: Select all
total[1s, 2s, 3s, 4s, 5s, 8s]0    [0, 0, 0, 0, 0, 0]10   [0, 0, 0, 0, 2, 0]20   [0, 0, 1, 1, 1, 1]30   [0, 0, 1, 1, 3, 1]10   [0, 0, 2, 1, 0, 0]20   [0, 0, 2, 1, 2, 0]10   [0, 1, 0, 0, 0, 1]20   [0, 1, 0, 0, 2, 1]10   [0, 1, 1, 0, 1, 0]20   [0, 1, 1, 0, 3, 0]20   [0, 1, 2, 1, 0, 1]30   [0, 1, 2, 1, 2, 1]10   [1, 0, 0, 1, 1, 0]20   [1, 0, 0, 1, 3, 0]20   [1, 0, 2, 0, 1, 1]30   [1, 0, 2, 0, 3, 1]20   [1, 1, 0, 1, 1, 1]30   [1, 1, 0, 1, 3, 1]10   [1, 1, 1, 1, 0, 0]20   [1, 1, 1, 1, 2, 0]10   [2, 0, 0, 0, 0, 1]20   [2, 0, 0, 0, 2, 1]10   [2, 0, 1, 0, 1, 0]20   [2, 0, 1, 0, 3, 0]20   [2, 0, 2, 1, 0, 1]30   [2, 0, 2, 1, 2, 1]20   [2, 1, 1, 0, 1, 1]30   [2, 1, 1, 0, 3, 1]10   [2, 1, 2, 0, 0, 0]20   [2, 1, 2, 0, 2, 0]20   [3, 0, 0, 1, 1, 1]30   [3, 0, 0, 1, 3, 1]10   [3, 0, 1, 1, 0, 0]20   [3, 0, 1, 1, 2, 0]10   [3, 1, 0, 0, 1, 0]20   [3, 1, 0, 0, 3, 0]20   [3, 1, 1, 1, 0, 1]30   [3, 1, 1, 1, 2, 1]20   [3, 1, 2, 1, 1, 0]30   [3, 1, 2, 1, 3, 0]

I don't know what [4, 34]; [14, 24] refers to but that's not what you want.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12538
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### Re: Equal sum of a subset and remainder of a set

O ok thanks, I think I see what you mean;

What I meant is that, the sum of the subset has to end with 4, for it is 154. splitting 38 in 2 sums where both term end with 4, the options are [4, 34]; 4+34=38 and [14, 24];14+24=38
For the sum of non divisible elements is 38, it is not worth looking for a subset where the sum of elements divisible by 10 is 110 and 160 respectively; 110+160=270
the only possibilities are 120 and 150 resp.; and 130 and 140 resp.

For example
there is no subset 1 such that
subset 1 {10, 80, a, ..., n} where {a, ..., n} are a subset of the elements non-divisible by 10, for 10+80=90 such that the sum of remainder of the elements is 270-90=180
therefore there is no subset 2 {20,20,30,50,60, m, ..., x} where {m, ..., x} are the remainder of elements of the set that are not divisible by 10. Now, you don't have to loop over all of the possible values of the large multiples of ten until one works.
Hoempa
Super User

Posts: 1700
Joined: Thu Apr 01, 2010 9:38 am

### Re: Equal sum of a subset and remainder of a set

Hoempa wrote:What I meant is that, the sum of the subset has to end with 4, for it is 154.

OK, that's the same as what I did but with 4, 14, 24, 34 instead of 0, 10, 20, 30.

For the faster (but higher memory) approach you split into two roughly equal groups -- actually what you want to equalize is product(# of times a number is repeated + 1). Since there are so few numbers it's probably worth solving exactly (this can be done with a knapsack-type algorithm using weights equal to log(1 + #)). For one group (the slightly smaller), calculate all possible totals and store them in a lookup table where you can quickly find if a sum is present and, if so, find which elements it uses. For the other group, loop through all possibilities. For each with sum x, check if 4 - x, 14 - x, 24 - x, and 34 - x are present in the lookup table, and if so store them in a new lookup table with the combined elements.

Now you use this lookup table with the multiples of ten just like before.

---

Alternately, for increased speed you *might* want to split the multiples of ten into two groups (large and small) so that the product(# of times a number is repeated + 1) for the large table is about the same as the analogous product for the small table times the number of elements in the lookup table. Then make a new lookup table combining the current lookup table with all combinations from the small group, then combine the large group with the lookup table.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12538
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### Re: Equal sum of a subset and remainder of a set

In the weekend I have done some testing, and I have both positive and negative conclusions.

Hopefully I do not offend anyone, however it seems the original problem of the sum sets is not really applying anymore. I thought I needed the sum set to check of a set of numbers would be balanced with the others. However, I need also most kind of combinations. Therefor, it was a lot easier to make all possible combinations for one group and divide them into sets of the same sum. Then I could combine all these combinations of one 'sum' group to any other of the same 'sum' group and I don't have to calculate whether they have the same sum. Because I would get an enormous amount of groups I limited the max number of elements to be 7 (which is enough in my case). I only have to calculate for any combination if I have enough of them (i.e. if one group is { 2, 4} and the other group is also { 2, 4}, I have to check that I have two 2's and two 4's but this is a quite easy calculation. In my current setup, these combinations can be done within 1 second. It might increase when I have more items (numbers). If that is the case, I probably might use some of the set splitting algorithms as mentioned by you.

Because I don't want to 'cause any more work without need', I really have to think further about the rest of the problem (which are some calculations with these sets I generated). Before I will ask help again, I will make sure I know what to calculate (so I will first make the program/algorithm so it works ... possibly very ineffeciently, and after that asking for help to improve it).

Thanks for all the help, and it will either come in handy for me later, I learned a lot of it and possibly you liked the discussion too.
Btw, of course the discussion don't need to be stopped ... but it can take some time before I will/have to use all the algorithm improvements mentioned by you all.
michelkeijzers
Newcomer

Posts: 12
Joined: Mon Jan 31, 2011 4:50 am

### Re: Equal sum of a subset and remainder of a set

Glad to hear it. I completely agree -- if you're working with numbers small enough that a basic algorithm finishes in 1 second, and that's good enough, there's no need to over-engineer a solution.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12538
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### Re: Equal sum of a subset and remainder of a set

Good to see you have a solution for now. I liked to investigate some more on this though, so there is need to worry about that
Hoempa
Super User

Posts: 1700
Joined: Thu Apr 01, 2010 9:38 am

### Re: Equal sum of a subset and remainder of a set

Thank you very much for all the help again ... I will think a further problem later and I might need some help for that too. And then it might be possible I need a better solution for the original problem (so then I still use all the proposals you made).

I think the next problem will be a bit kind of how a chess program work to make it quicker. However I'm still figuring out how to write it down a little more mathematically. Also, I have very little time the next month, so I will be a little less active.

Worst case solution I could come up now is something like:
p: possibilities (averaged) for a certain weight
n: number of positions to order the weights per side
e: number of exercises

((p * n!^2) ^ 2) ^ e

typically, p = 50, n = 6, e = 10

which results in (50 * 6!^2) ^ 11 = 3,5e81
... guess I need some optimization

Greetings,

Michel
michelkeijzers
Newcomer

Posts: 12
Joined: Mon Jan 31, 2011 4:50 am

Previous