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

• TylerH
In summary, the false conjecture mentioned is that for any natural number, there exists a sum of 4 square integers that can be represented by that number.
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 said:
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's_sum_of_powers_conjecture

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.

Last edited:
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).

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.

morphism said:
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.
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.

morphism said:
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.
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.

Last edited:
ramsey2879 said:
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.
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.

## 1. How is the minimum number of elements to sum to all elements in another set determined?

The minimum number of elements to sum to all elements in another set is determined by finding the smallest subset of elements in the first set that can be combined to equal each element in the second set. This subset must include at least one element for each unique element in the second set.

## 2. Is there a formula or equation for calculating the minimum number of elements?

There is no specific formula or equation for calculating the minimum number of elements to sum to all elements in another set. It typically involves determining the unique elements in the second set and finding a combination of elements from the first set that equals each of these elements.

## 3. Can the minimum number of elements change for different sets?

Yes, the minimum number of elements can change for different sets. It depends on the specific elements in each set and their values. Some sets may require fewer elements to sum to all elements in another set, while others may require more.

## 4. Is there a limit to the minimum number of elements that can be used?

There is no limit to the minimum number of elements that can be used to sum to all elements in another set. However, the minimum number will always be at least one for each unique element in the second set.

## 5. Can the minimum number of elements be greater than the number of elements in the second set?

Yes, it is possible for the minimum number of elements to be greater than the number of elements in the second set. This can occur if there are duplicate elements in the second set that require multiple elements from the first set to sum to them.

Replies
0
Views
313
Replies
2
Views
1K
Replies
15
Views
4K
Replies
8
Views
1K
Replies
39
Views
2K
Replies
3
Views
1K
Replies
12
Views
1K
Replies
5
Views
2K
Replies
11
Views
2K
Replies
9
Views
2K