Register to reply

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

by TylerH
Tags: elements, minimum, number
Share this thread:
TylerH
#1
Mar8-12, 09:30 PM
P: 737
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.
Phys.Org News Partner Science news on Phys.org
What lit up the universe?
Sheepdogs use just two simple rules to round up large herds of sheep
Animals first flex their muscles
morphism
#2
Mar8-12, 10:53 PM
Sci Advisor
HW Helper
P: 2,020
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
#3
Mar9-12, 02:07 AM
P: 737
Quote Quote by morphism View Post
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
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
#4
Mar9-12, 11:36 AM
P: 737
Minimum number of elements to in one set to sum to all in another.

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
#5
Mar9-12, 05:00 PM
Sci Advisor
HW Helper
P: 2,020
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
#6
Mar9-12, 09:32 PM
P: 737
Quote Quote by morphism View Post
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.
ramsey2879
#7
Mar11-12, 05:17 PM
P: 894
Quote Quote by morphism View Post
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.
TylerH
#8
Mar13-12, 10:58 PM
P: 737
Quote Quote by ramsey2879 View Post
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.


Register to reply

Related Discussions
Minimum number of edges in a graph of order n with chromatic number k Set Theory, Logic, Probability, Statistics 1
Number of elements in group Calculus & Beyond Homework 23
Number of elements in a set General Math 5
Minimum number of common elements in sets Set Theory, Logic, Probability, Statistics 2
Number of 2-elements Linear & Abstract Algebra 0