1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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