Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 8, 2012 #1
    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.
     
  2. jcsd
  3. Mar 8, 2012 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

  4. Mar 9, 2012 #3
    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: Mar 9, 2012
  5. Mar 9, 2012 #4
    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).
     
  6. Mar 9, 2012 #5

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Mar 9, 2012 #6
    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.
     
  8. Mar 11, 2012 #7
    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: Mar 11, 2012
  9. Mar 13, 2012 #8
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Minimum number of elements to in one set to sum to all in another.
Loading...