Minimum number of elements to in one set to sum to all in another.

TylerH

Is there a name for the concept of trying to find the minimum number of elements from one set of integers that will sum to all elements in another set? Like, for example, with the Pythagorean Theorem, this would be to find the minimum number of elements from the set of all squared integers that will sum to all squared integers; the answer would be two.

I'm asking because I'm looking into how to extend the Pythagorean Theorem to higher powers. I know FLT has been proven, so I know that for all powers higher than 2, the answer must be that one must sum more than 2 number.

EDIT: Title should be: "Minimum number of elements in one set to sum to all in another.

morphism

I don't know if there's any standard terminology that applies here. However, I wanted to point out the following false conjecture in case you're not aware of it: http://en.wikipedia.org/wiki/Euler%2...ers_conjecture

TylerH

Thanks. That's similar. To restate in the variables and formulas there: I'm looking to see if I can find n for a given k such that a_i can be found for any b.

But, even though that is my goal, I'm programming it in such a way that it will work with arbitrary sets of numbers, to find the minimum number of elements, n, from set A such that there exists a1, ..., an such that a1 + ... + an = b for any b in a set B.

Another interesting question I though about tackling is maybe seeing if I can find a generalization of Lagrange's Four-Square Theorem.

Once I finish the code, I'll post it here.

TylerH

Is Lagrange's Four Square theorem even valid? I know that sounds like a stupid question, to question a theorem, but I've found that it takes 5 squares for multiple numbers.

23: 16 4 1 1 1
32: 25 4 1 1 1
43: 36 4 1 1 1
48: 36 9 1 1 1
56: 49 4 1 1 1
61: 49 9 1 1 1
71: 64 4 1 1 1
76: 64 9 1 1 1
79: 64 9 4 1 1
88: 81 4 1 1 1
93: 81 9 1 1 1
96: 81 9 4 1 1

Am I misunderstanding its statement or something? I interpreted it to mean that any natural number can be represented as the sum of 4 square integers, but that obviously isn't true for 23 (16 + 4 + 1 + 1 + 1).

morphism

Just because you can represent 23 as the sum of five squares doesn't mean you can't represent it as the sum of 4 squares... In fact, 23 = 3^2 + 3^2 + 2^2 + 1^2.

TylerH

Oh! My algorithm is flawed. I assumed that one would want to maximize the usage of larger terms. (Use 16 before 9, for example.) I'll have to work out how to fix this. It's going to make the complexity a lot worse.

ramsey2879

I think your coding problem would be simpler if you programmed it to always choose the the smallest possible element first, i.e. first look at 1,1,1,x^2 if there isn't an x^2 then look at 1,1,4,x^2 then if there isn't an x^2 increment the 4 up to a 9 or 16, when you run out of increments of the third element, i.e. no x^2 for 1,1,16 then try incrementint the 2nd and third element to a 4, i.e. 1,4,4,x^2. when you find that there is no x^2 you would natually increment the third element to a 9 and find a solution. This method would work every time.

Sorry I meant to Quote the OP's last post.

TylerH

That would be a good way for finding sums of n numbers that sum to number of a given power, but it wouldn't work the other way around: finding n for a given power.