Find all possible terms of a given sum

[atrus_ovis]

Homework Statement

Say we have a given sum, S.
I have to, as part of a more general problem in a program, find all possible distinct terms x₁,x₂,x₃,x₄ which when added, give that sum, and the ways they can be rearranged.
Meaning i have to find all 4-tuples that adding one's members gives S.
Term t>=1
For example, for S=10 , terms are 1,2,3,4.
1+2+3+4=10, so all possible tuples are the permutations of 1,2,3,4 which gives us 24 4-tuples

Don't know if it's relevant, but the terms are bounded by a user given number N.
I don't know if such a formula exists or if I'm supposed to find them by exhaustive search, so i turn to you in case the 1st way is doable.

Homework Equations

the permutations formula?
P(n,r) = n! / (n-r)!

The Attempt at a Solution

Haven't accomplished much.
Since S is arbitrary (user-given), i'll have to find a way to generate all valid terms from s.
Since we have 4 slots for the terms, and each term is distinct and greater than 1,
A 'minimum' case would be:
the 3 smallest terms would be 1,2,3 and the remaining S-6

Often in such problems i try a few examples and try to find out patterns.
10-> 1,2,3,4. 24 ways
11-> 1,2,3,5 same
..
14->(1,2,3,8) 24 ways , 2,3,4,5 24 ways

but with no luck..

 

[chaoseverlasting]

After nuking the problem, another, simpler thought struck me. If your system is restricted to 4 terms (x1,x2,x3,x4), let these terms be in an AP. If this is the case, it is always easy to define as 4x1+6d=S.

Using this above equation, we can find out the points where the number of possibilities increases.

For all |d|>0, you will get a distinct series. The idea is simple, you use an AP to get a distinct series, and based on the value of d, you add/subtract the various terms of the series to get all other possible, unique series.

For these points, where x1=1 and d>0, we have several AP's which will satisfy our requirements. Say, we look at S=16. One of these
is for d=2. (1,3,5,7). If we solve for d=1, we get x1=2.5 which is not an integer so this case must be rejected.

Next, if the common difference is greater than one, each of the numbers can be added or subtracted by 1 and all other integers less than the common difference.

Which means,
if d=k (some integer), each of the terms of the ap can be increased or decreased by an integer 0<i<k such that the sum remains unaltered. Obviously, if you increase x1 by i then you must decrease x2 by i to maintain the sum.

One possible shortcoming of this is if you increase x2 by i and decrease x3 by i you may get x2+i==x3-i. For example, in the above series, if you increase 3 by one and reduce 5 by one, you get x2=x3=4, which is unacceptable. As such, I would recommend that you increase and decrease x1,x3 simultaneously and x2,x4 simultaneously to bypass the above problem.

The above algorithm should give you the required distinct terms for all even values of the sum. For odd values of S, you can eliminate redundant cases based on conditions on d and i. It's a little late and I'm tired and a little beyond my faculties at the moment, but I think that the expression would be similar to the inclusion-exclusion principle.

I hope this is enough to get you started and work the rest of it out. I would tend to think that another more elegant solution to your problem is available because this too seems a little messy. It will work, however, and its a decent place to start.

 

[atrus_ovis]

Thanks chaoseverlasting.
By AP & wiki's help i assume you mean arithmetic progression.

I'll read on and study the solution you proposed to understanding and get back at you.