Summing of digits in numbers

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Supergrunch
Posts: 135
Joined: Mon Nov 19, 2007 5:17 pm UTC
Location: Cambridge, UK
Contact:

Summing of digits in numbers

Postby Supergrunch » Fri Feb 29, 2008 8:54 pm UTC

Someone on another forum was asking for help with a question - how many five-digit numbers have digits that sum to 39? I googled this and found that the question first asked you to show that 15 five-digit numbers sum to 43. This intrigued me because I had no idea how to approach it, though I'll post some of my reasonably futile scribblings:

You can represent the digit sum as x1 + x2 + x3 + x4 + x5 = 39, where xi is an integer between 0 and 9 inclusive. Now this is all well and good, but doesn't really help me... Obviously if I find one number that sums to 39, then I can do combination stuff to include all the possible arrangements of digits, but this isn't very methodical. Something tells me there's a neat way of doing this that I'm failing to see.

Discuss.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Summing of digits in numbers

Postby jestingrabbit » Fri Feb 29, 2008 9:23 pm UTC

For 43:
Spoiler:
Note that we're only 2 off from the most that the sum can be, so you've gotta count the number of ways that you can distribute the 2 that we need to subtract from the 5 digits that there are.

One way to get those 2 is to subtract them both from the same place. The other way is to get them from 2 different places. There's 5 ways to do the first, and 5 choose 2 = 10 ways to do the second. So you get 15 ways in total.


For 39:
Spoiler:
You're 6 off, so you've gotta look at each of the ways to distribute those six that we're off by ie
6 -> 5
5+1 -> 20
4+2 -> 20
4+1+1 -> 5*4C2=30
3+3 -> 5C2=10
3+2+1 -> 5*4*3=60
3+1+1+1 -> 5*4C3=20
2+1+1+1+1 -> 5
1+1+1+1+1+1 -> 0
which comes to a total of 170.

Edit: thanks sumudu, forgot
2+2+1+1 -> 5C2*3C2=30
2+2+2 -> 5C3=10

for a total of 210... Sumudu has the better technique.
Last edited by jestingrabbit on Fri Feb 29, 2008 10:55 pm UTC, edited 3 times in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Sumudu
Posts: 2
Joined: Fri Feb 29, 2008 9:54 pm UTC

Re: Summing of digits in numbers

Postby Sumudu » Fri Feb 29, 2008 10:00 pm UTC

Your math is off somewhere...
Spoiler:
...but the idea of looking at it as taking away from 99999 is a good one (though it gets problematic if you're taking away more than 8, since then you have to deal with leading zeroes).

Since we are looking to distribute 6 -1's among 5 digits, the easiest analysis is to imagine we have 10 dots, 4 of which we will turn into vertical lines. These lines will separate the remaining 6 dots into five groups, one for each digit. There are obviously (10 Choose 4) ways to do this, which gives 210 as the answer.

For 43, we are distributing just 2 -1's, so we have (6 Choose 4) = 15.

olcaddy
Posts: 21
Joined: Tue Feb 26, 2008 8:24 pm UTC

Re: Summing of digits in numbers

Postby olcaddy » Sat Mar 01, 2008 3:26 am UTC

I'm sure this is cheating but I don't feel like studying for exams and this seemed like fun.
Spoiler:
Image

List of sums 1-45
Spoiler:
    BIN SUM
    1 1
    2 5
    3 15
    4 35
    5 70
    6 126
    7 210
    8 330
    9 495
    10 714
    11 992
    12 1330
    13 1725
    14 2170
    15 2654
    16 3162
    17 3675
    18 4170
    19 4620
    20 4998
    21 5283
    22 5460
    23 5520
    24 5460
    25 5283
    26 4998
    27 4620
    28 4170
    29 3675
    30 3162
    31 2654
    32 2170
    33 1725
    34 1330
    35 992
    36 714
    37 495
    38 330
    39 210
    40 126
    41 70
    42 35
    43 15
    44 5
    45 1

Brinny
Posts: 13
Joined: Sun Mar 02, 2008 2:15 am UTC

Re: Summing of digits in numbers

Postby Brinny » Sun Mar 02, 2008 5:43 am UTC

Sumudu wrote:Your math is off somewhere...
Spoiler:
...but the idea of looking at it as taking away from 99999 is a good one (though it gets problematic if you're taking away more than 8, since then you have to deal with leading zeroes).

Since we are looking to distribute 6 -1's among 5 digits, the easiest analysis is to imagine we have 10 dots, 4 of which we will turn into vertical lines. These lines will separate the remaining 6 dots into five groups, one for each digit. There are obviously (10 Choose 4) ways to do this, which gives 210 as the answer.

For 43, we are distributing just 2 -1's, so we have (6 Choose 4) = 15.


Wow, I hadn't thought of it that way before. I tried to brute force the problem by counting the number of cases you can get without the restriction 0 <= xi <= 9 and then count the number of violations of the restrictions (the calculations got to be very cumbersome past sum = 20). The method of distributing -1's is a very clever one!

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Summing of digits in numbers

Postby jaap » Sun Mar 02, 2008 7:54 am UTC

Brinny wrote:Wow, I hadn't thought of it that way before. I tried to brute force the problem by counting the number of cases you can get without the restriction 0 <= xi <= 9 and then count the number of violations of the restrictions (the calculations got to be very cumbersome past sum = 20). The method of distributing -1's is a very clever one!


You run into the same problem as soon as you try a sum of less than 36, because you are then distributing more than nine -1's and they cannot all be assigned to the same digit.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Summing of digits in numbers

Postby jestingrabbit » Sun Mar 02, 2008 10:55 am UTC

jaap wrote:
Brinny wrote:Wow, I hadn't thought of it that way before. I tried to brute force the problem by counting the number of cases you can get without the restriction 0 <= xi <= 9 and then count the number of violations of the restrictions (the calculations got to be very cumbersome past sum = 20). The method of distributing -1's is a very clever one!


You run into the same problem as soon as you try a sum of less than 36, because you are then distributing more than nine -1's and they cannot all be assigned to the same digit.

and you can't put 9 -1's on the first digit either, because then you've got less than 5 digits.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Brinny
Posts: 13
Joined: Sun Mar 02, 2008 2:15 am UTC

Re: Summing of digits in numbers

Postby Brinny » Sun Mar 02, 2008 10:03 pm UTC

jestingrabbit wrote:
jaap wrote:
Brinny wrote:Wow, I hadn't thought of it that way before. I tried to brute force the problem by counting the number of cases you can get without the restriction 0 <= xi <= 9 and then count the number of violations of the restrictions (the calculations got to be very cumbersome past sum = 20). The method of distributing -1's is a very clever one!


You run into the same problem as soon as you try a sum of less than 36, because you are then distributing more than nine -1's and they cannot all be assigned to the same digit.

and you can't put 9 -1's on the first digit either, because then you've got less than 5 digits.


Yes, one of the other things that made the calculation particularly cumbersome once you hit 20. There were too many different types of violations to account for, and you had to make sure each violation was a) distinct and b) that you accounted for every violation that exists. The method works well for the first 20, but rapidly breaks down afterwards. Furthermore, it seems to be better suited for problems that involve summing digits between 1 and 10^n as opposed to summing digits for an n-digit number.

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: Summing of digits in numbers

Postby imatrendytotebag » Sun Mar 02, 2008 10:59 pm UTC

Spoiler:
If you have n s-sided dice and want to roll k, the number of ways of doing that is:
sum(i = 0, [(k-n)/s]) (-1)^i*C(k-si-1,n-1). Call this f(n,s,k). Note: [x] denotes floor of x, and C(a,b) is a choose b. Now:

We essentially have five ten-sided dice, however this formula uses dice numbered 1-n, so we bump each digit up (rolling a "1" means you put a 0 in the number, rolling a "10" means you put a 9 in the number, etc.) So for rolling a 39 there are f(5,10,39+5) = f(5,10,44) ways.

This method generalizes well. If we want to know how many n-digit numbers have a digit sum of k, its f(n,10,k+n) - f(n-1,10,k+n-1). (Note: the subtraction is to take care of cases where there are leading zeroes).

Also, for problems where the sum is closer to the maximum than the minimum (ie 39 is closer to 45 than 0), its helpful to notice f(n,s,k) = f(n,s,(s+1)*n - k).
Hey baby, I'm proving love at nth sight by induction and you're my base case.

User avatar
0xDEADBEEF
Posts: 284
Joined: Wed Jan 30, 2008 6:05 am UTC
Location: Austin, TX
Contact:

Re: Summing of digits in numbers

Postby 0xDEADBEEF » Mon Mar 03, 2008 5:00 am UTC

Supergrunch wrote:Someone on another forum was asking for help with a question - how many five-digit numbers have digits that sum to 39? I googled this and found that the question first asked you to show that 15 five-digit numbers sum to 43.


I like programming far, far better than discrete math, so my first thought was, it would take a few milliseconds for a computer to brute-force its way through 99,000 possibilities.

In python, one line should do the trick: (It's really one line, even if the board software word-wraps it!)

Code: Select all

[i for i in range(10000, 100000, 1) if (i%10 + i/10%10 + i/100%10 + i/1000%10 + i/10000%10 == 43)]


The result is:
[79999,
88999,
89899,
89989,
89998,
97999,
98899,
98989,
98998,
99799,
99889,
99898,
99979,
99988,
99997]

But seeing that, when you think of it, three of the digits have to be nines. The digits in 88888 just add up to 40. So if you think in your head about "9999x", the x has to be a 7. And then, if you remember that the "7" could be in any position, you've got 5 permutations right there. The other way to add up to 43 is three "9's" and two "8's". When you arrange them in every possible position, you've got ten more answers.

That's why the article that you found suggested starting with "43." It's easier to wrap your head around that the possibilities for "39." But now, if you take every set of 5 digits that adds to 39, and "derange" them in every possible combination, you'll have your answer.

Code: Select all

len([i for i in range(10000, 100000, 1) if (i%10 + i/10%10 + i/100%10 + i/1000%10 + i/10000%10 == 39)])

...says that there are 210 possible answers for 39.

Edit: Changed the "39" to a "43" in the first "one-liner." Doh!
Last edited by 0xDEADBEEF on Mon Mar 03, 2008 11:58 pm UTC, edited 1 time in total.

Brinny
Posts: 13
Joined: Sun Mar 02, 2008 2:15 am UTC

Re: Summing of digits in numbers

Postby Brinny » Mon Mar 03, 2008 7:59 pm UTC

0xDEADBEEF wrote:
Supergrunch wrote:Someone on another forum was asking for help with a question - how many five-digit numbers have digits that sum to 39? I googled this and found that the question first asked you to show that 15 five-digit numbers sum to 43.


I like programming far, far better than discrete math, so my first thought was, it would take a few milliseconds for a computer to brute-force its way through 99,000 possibilities.

In python, one line should do the trick: (It's really one line, even if the board software word-wraps it!)

Code: Select all

[i for i in range(10000, 100000, 1) if (i%10 + i/10%10 + i/100%10 + i/1000%10 + i/10000%10 == 39)]


The result is:
[79999,
88999,
89899,
89989,
89998,
97999,
98899,
98989,
98998,
99799,
99889,
99898,
99979,
99988,
99997]

But seeing that, when you think of it, three of the digits have to be nines. The digits in 88888 just add up to 40. So if you think in your head about "9999x", the x has to be a 7. And then, if you remember that the "7" could be in any position, you've got 5 permutations right there. The other way to add up to 43 is three "9's" and two "8's". When you arrange them in every possible position, you've got ten more answers.

That's why the article that you found suggested starting with "43." It's easier to wrap your head around that the possibilities for "39." But now, if you take every set of 5 digits that adds to 39, and "derange" them in every possible combination, you'll have your answer.

Code: Select all

len([i for i in range(10000, 100000, 1) if (i%10 + i/10%10 + i/100%10 + i/1000%10 + i/10000%10 == 39)])

...says that there are 210 possible answers for 39.


Haha, step 2: writing AI to prove Riemann's hypothesis...

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Summing of digits in numbers

Postby Ended » Mon Mar 03, 2008 8:36 pm UTC

Brinny wrote:Haha, step 2: writing AI to prove Riemann's hypothesis...

Easy.

Spoiler:

Code: Select all

//pseudocode

for each z in C
{
  if( zeta(z)==0 && is_nontrivial(z) && real_part(z)!=0.5 )
  {
    print "Riemann FTL, Oh me yarm."
    exit
  }
}
print "Riemann FTW, meh."

//TODO: fix infinite loop.

So as not to be entirely off-topic, the OP's problem is somewhat related to that of calculating the partition function for an integer N, i.e. how many distinct ways N can be represented as the sum of positive integers. This produces my all-time favourite "what??!! IT BREAKS MY MIND" formula, Rademacher's Series.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Summing of digits in numbers

Postby btilly » Mon Mar 03, 2008 8:54 pm UTC

0xDEADBEEF wrote:
Supergrunch wrote:Someone on another forum was asking for help with a question - how many five-digit numbers have digits that sum to 39? I googled this and found that the question first asked you to show that 15 five-digit numbers sum to 43.


I like programming far, far better than discrete math, so my first thought was, it would take a few milliseconds for a computer to brute-force its way through 99,000 possibilities.

In python, one line should do the trick: (It's really one line, even if the board software word-wraps it!)

Code: Select all

[i for i in range(10000, 100000, 1) if (i%10 + i/10%10 + i/100%10 + i/1000%10 + i/10000%10 == 39)]

I'm reminded of an old saying. "All proofs are one-liners if you start far enough to the left."
I'm also very tempted to write

Code: Select all

perl -le'use List::Util"sum";sum(split//)==39&&print for 1e4..1e5'|wc

0xDEADBEEF wrote:The result is:
[79999,
88999,
89899,
89989,
89998,
97999,
98899,
98989,
98998,
99799,
99889,
99898,
99979,
99988,
99997]

Confusion alert! That output is for a different line of code than the one you display! (You gave the sum=39 line of code and the sum=43 result set.)

0xDEADBEEF wrote:But seeing that, when you think of it, three of the digits have to be nines. The digits in 88888 just add up to 40. So if you think in your head about "9999x", the x has to be a 7. And then, if you remember that the "7" could be in any position, you've got 5 permutations right there. The other way to add up to 43 is three "9's" and two "8's". When you arrange them in every possible position, you've got ten more answers.

That's why the article that you found suggested starting with "43." It's easier to wrap your head around that the possibilities for "39." But now, if you take every set of 5 digits that adds to 39, and "derange" them in every possible combination, you'll have your answer.

Code: Select all

len([i for i in range(10000, 100000, 1) if (i%10 + i/10%10 + i/100%10 + i/1000%10 + i/10000%10 == 39)])

...says that there are 210 possible answers for 39.

And so there are. :-)
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Summing of digits in numbers

Postby Cosmologicon » Mon Mar 03, 2008 9:19 pm UTC

Yet another one-line solution:

Code: Select all

seq 99999|sed 's/./+\0/2g;'|bc|grep 39|wc -l

And to get the histogram:

Code: Select all

seq 99999|sed 's/./+\0/2g;'|bc|sort -n|uniq -c

I, however, find doing the discrete math more interesting than these.

Brinny
Posts: 13
Joined: Sun Mar 02, 2008 2:15 am UTC

Re: Summing of digits in numbers

Postby Brinny » Mon Mar 03, 2008 10:31 pm UTC

Cosmologicon wrote:Yet another one-line solution:

Code: Select all

seq 99999|sed 's/./+\0/2g;'|bc|grep 39|wc -l

And to get the histogram:

Code: Select all

seq 99999|sed 's/./+\0/2g;'|bc|sort -n|uniq -c

I, however, find doing the discrete math more interesting than these.


I also find the discrete math/combinatorics behind it to be more interesting, but there is still value to brute-forcing I suppose =P.

User avatar
0xDEADBEEF
Posts: 284
Joined: Wed Jan 30, 2008 6:05 am UTC
Location: Austin, TX
Contact:

Re: Summing of digits in numbers

Postby 0xDEADBEEF » Tue Mar 04, 2008 12:00 am UTC

btilly wrote:Confusion alert! That output is for a different line of code than the one you display! (You gave the sum=39 line of code and the sum=43 result set.)


I was just checking to see if everyone was paying attention! 8)


It's fixed, now. :oops:

User avatar
Nimz
Posts: 580
Joined: Thu Aug 02, 2007 9:49 am UTC
Location: the origin

Re: Summing of digits in numbers

Postby Nimz » Wed Mar 05, 2008 10:42 am UTC

Wouldn't the simplest non-bruteforce method for calculating number of ways to get all the sums be to use generating functions?
g1=x+x2+x3+x4+x5+x6+x7+x8+x9
g2=1+x+x2+x3+x4+x5+x6+x7+x8+x9
g3=1+x+x2+x3+x4+x5+x6+x7+x8+x9
g4=1+x+x2+x3+x4+x5+x6+x7+x8+x9
g5=1+x+x2+x3+x4+x5+x6+x7+x8+x9
where the coefficient of xj in gi is the number of ways of having the number j appear in the i'th digit.

f=g1*g2*g3*g4*g5
=(x(1-x9)/(1-x))*((1-x10)/(1-x))*((1-x10)/(1-x))*((1-x10)/(1-x))*((1-x10)/(1-x))
=(1/(1-x))5*x*(1-x9)(1-x10)(1-x10)(1-x10)(1-x10)
=(1/(1-x))5(x-x10)(1-4x10+6x20-4x30+x40)
=(1/(1-x))5(x-x10-4x11+4x20+6x21-6x30-4x31+4x40+x41-x50)
=(sumk(C(k+5,5)*xk))(x-x10-4x11+4x20+6x21-6x30-4x31+4x40+x41-x50)
where C(n,r) = n!/((n-r)! r!)

From here we can see that the coefficient of xj = C(j+4,5) - C(j-5,5) - 4C(j-6,5) + 4C(j-15,5) + 6C(j-16,5) - 6C(j-25,5) - 4C(j-26,5) + 4C(j-35,5) + C(j-36,5) - C(j-45,5). This should be the same as the number of 5-digit numbers that has a sum of digits = j. This is clearly true for j=1, and with a little effort it gives the clearly wrong answer of 136511 when j=45 (Can't accuse me of trying to hide my mistake :mrgreen: ). I'm too tired to find my mistake right now, but the idea is there, at any rate. I still maintain that the simplest non-bruteforce method for getting ALL of them is via generating functions, though.

Of course, you could expand f directly by multiplying the g's as originally given. But that would be almost as much work as the original problem...
LOWA

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: Summing of digits in numbers

Postby Tirian » Wed Mar 05, 2008 5:14 pm UTC

Nimz wrote:Wouldn't the simplest non-bruteforce method for calculating number of ways to get all the sums be to use generating functions?


It's been a while, but back when I took Combinatorics the non-bruteforce solution of choice was the Inclusion-Exclusion Principle. Namely, there are A = C(43, 4) ways to throw thirty-nine (non-distinct) tokens into five (distinct) boxes, B = C(33, 4) ways to throw thirty-nine tokens into five boxes knowing in advance that at least one of the boxes had at least ten tokens, C = C(23,4) ways if at least two boxes were known to be overloaded, and so on. And then the solution you're looking for is X = A - C(5, 1) B + C(5,2) C - C(5,3) D + ....

Okay, in this specific problem you have to then go on to calculate the number of four-digit numbers to rule out five-digit numbers with leading zeroes, but even that is simpler than generating functions.

(As I say, it's been a while, so I may have booched a number here or there, but the overriding technique is still sound.)

User avatar
Nimz
Posts: 580
Joined: Thu Aug 02, 2007 9:49 am UTC
Location: the origin

Re: Summing of digits in numbers

Postby Nimz » Thu Mar 06, 2008 1:10 pm UTC

Actually, working out what the generating function is directly isn't as bad as I first thought. After all, squaring 1+...+x9 and squaring that answer gets you most of the way there. Then you just multiply that answer by x+...+x9. I got as far as squaring the first time and starting with squaring the second time earlier, but I got distracted.

That inclusion-exclusion principle stuff is all well and good, but it only gives you one answer at a time. Your example should give the proper result for a sum of digits = 39, but a generating function would give you the result for ANY sum of digits. Not that we don't already have every answer...
olcaddy wrote:List of sums 1-45
Spoiler:
    BIN SUM
    1 1
    2 5
    3 15
    4 35
    5 70
    6 126
    7 210
    8 330
    9 495
    10 714
    11 992
    12 1330
    13 1725
    14 2170
    15 2654
    16 3162
    17 3675
    18 4170
    19 4620
    20 4998
    21 5283
    22 5460
    23 5520
    24 5460
    25 5283
    26 4998
    27 4620
    28 4170
    29 3675
    30 3162
    31 2654
    32 2170
    33 1725
    34 1330
    35 992
    36 714
    37 495
    38 330
    39 210
    40 126
    41 70
    42 35
    43 15
    44 5
    45 1
LOWA

The Laughing Man
Posts: 5
Joined: Sat Dec 29, 2007 6:15 pm UTC

Re: Summing of digits in numbers

Postby The Laughing Man » Thu Mar 06, 2008 9:31 pm UTC

Well, using combinatorics I get a general solution of f(d,S)=Sum[C(d,n)C(10d-1-S-10n,d-1)(-1)n,n=0..floor((9d-S)/10)] where d is the number of digits and S is their sum. This, however, allows for leading zeros, if you want a solution that doesn't, it's just f(d,S)-f(d-1,S).

I used the method of distributing -1s for this, which gives C(10d-1-S,d-1), but this allows for digits less than 0. We can easily see that the number of distributions with at least 1 digit<0 is C(d,1)*C(10d-1-S-10,d-1) (actually it's not, since it counts distributions with more than 1 digit<0 multiple times, but I'll get to that), the number of distributions with at least 2 digits<0 is C(d,2)*C(10d-1-S-20,d-1), and so on. Anyway, since the term for n=1 counts elements from the term n=2, we don't just subtract everything, hence the (-1)n. I apologize for this all being very hand-wavy, but the actual derivations for these are a good bit larger than I want to type.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests