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

All possible ways to sum to a number

  1. Feb 25, 2013 #1
    I am curious if there is a universal formula to find all possible sums of a given number. For instance, to add to 10:
    1+9
    2+8
    1+1+8
    2+2+2+3+1, etc

    I came up with a simple algorithm, but I'm sure there is something similar to Gauss's formula which can be utilized. I have heard Partitions used in number theory, but I don't know much about them beyond the fact that they are related to a similar problem.
     
  2. jcsd
  3. Feb 25, 2013 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

  4. Feb 25, 2013 #3

    pwsnafu

    User Avatar
    Science Advisor

    Yes, Rademacher's formula. See micromass's link.
     
  5. Feb 27, 2013 #4
    There's a lovely theorem by Euler about the sums of a given number:

    Count the number of ways a number may be represented as a sum of distinct integers. Then count the number of ways that number may be represented as a sum of odd but not necessarily distinct integers. The number of ways is the same in both cases.

    For example take the number 7. Using distinct integers 7 may be represented as

    7=7
    =6+1
    =5+2
    =4+3
    =4+2+1

    5 ways.

    Now we try with only the odd integers removing the restriction that they be distinct

    7=7
    =5+1+1
    =3+3+1
    =3+1+1+1+1
    =1+1+1+1+1+1+1

    5 ways. Unfortunately I can't remember the proof and I'm too lazy to have a bash at it myself.
     
  6. Feb 27, 2013 #5
    Well heres something that might help (or not)

    I did something with interative sums (liek 4 + 5 + 6, or 12+13, or 23+24+25+26+27) that always differ by one (and only integers)

    So for 23, the only iterative sum is 11 + 12

    For 26, its 5+6+7+8

    Its basically related to the factors of the number...

    Take 23 for instance... Its only factor is 1

    Add 1 to the factor to get 2, then 23/2 = 11.5, then +- (1/2) from 11.5, to get 11 and 12

    11 + 12 = 23

    Take 35... the factors are 1,5,7,35....

    So you can have a linear sum of 5 terms that revolve around 7 (5 + 6 + 7 + 8 + 9) or a linear sum of 7 terms that revolve around 5 (2+3+4+5+6+7+8)...


    I cant remember the whole thing.... but I remember that it was inpossible for a linear iterative sum for anything of 2^n, like 2,4,8,16...

    I cant remember, I worked on it, but I can't remember what the exact thing I did...


    Idk, just thought I'd mention it, since your question reminded me of it...



    ... or take
     
  7. Feb 28, 2013 #6

    Bacle2

    User Avatar
    Science Advisor

    This is also called the problem of balls-in-boxes , i.e., you have n balls that you want to

    put in k boxes. Line up the balls , together with the boxes. Every line-up corresponds

    to an assignment of balls in boxes , e.g., if n=k , the line up : ball, box, ball, box,...

    ball, box corresponds to the assignment of exactly one ball for each box. In total,

    you have n+k-1 objects to assign ( n balls, k boxes, but subtract one, since

    after k-1 boxes have been used, there is only one way of filling the k-th box)

    any choice of k-1 spaces ( for the balls, or, by symmetry, of n spaces

    where the boxes boxen? * will go ) is an assignment of balls to boxes.

    There are (n+k-1) C (k-1) or (n+k-1) C n ways of doing this assignment.

    If you want to guarantee that no boxes are empty, throw-in one ball on each

    box and do the same process: you are left with : n+k-1-k = n-1 balls to put in

    the same k-1 boxes in (n-1) C (k-1) ways.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook