## 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

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.

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

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

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.

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

### Re: Summing of digits in numbers

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

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

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!

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

### Re: Summing of digits in numbers

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.

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

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

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.

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

### Re: Summing of digits in numbers

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.

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

### Re: Summing of digits in numbers

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

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

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

Easy.

Spoiler:

Code: Select all

`//pseudocodefor 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

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`

[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.

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

### Re: Summing of digits in numbers

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

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.

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

### Re: Summing of digits in numbers

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! It's fixed, now. Nimz
Posts: 580
Joined: Thu Aug 02, 2007 9:49 am UTC
Location: the origin

### Re: Summing of digits in numbers

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 ). 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

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.)

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

### Re: Summing of digits in numbers

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...
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

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.