# Determination quantity of integers, the sum of digits of which is equal to $N$

For a number in the range $1 \le N \le 36$, i want to find a quantity of four- digit numbers, the sum of digits of which is equal $N$.

I would be very grateful for the algorithm! Thank you!

-

Hint: One simple algorithm starts:

foreach $x ( 1000 .. 9999 ) { ... }  It may run about 0.1 second slower than figuring out the result in a smarter way, but that's easily saved by the faster development time. And you can tabulate the 36 results so you don't have to run it more than once anyway. - Thank you for your answer, Henning Makholm! – Aleksey Bykov Jan 14 '13 at 21:31 Try assembling the digits from the number. - Thank you for your answer, Loki Clock! – Aleksey Bykov Jan 14 '13 at 21:31 The generating function for these is $$f(x) = (x^1+x^2+\cdots+x^9)(x^0+x^1+x^2+\cdots+x^9)^3.$$ It will produce all answers at once and the coefficient$[z^N] f(x)$of the term with degree$N$gives you the count of four digit numbers that sum to$N.$For example,$[z^{11}] f(x) = 279.\$ This polynomial contains only 36 terms and you can compute it e.g. with a computer algebra system since 36 is a very reasonable size to work with. Or you could start with an array of coefficients and code the multiplication yourself. The point is that the problem dimension is not of an order that would cause difficulties, so it is not in need of optimization.

-
Thanks a lot for such a detailed answer, Marko Riedel! What you say is very important to me. Thank you! – Aleksey Bykov Jan 15 '13 at 0:51

Here is a C program (tested with gcc version 4.3.2) that will do the above computation.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
int n;

if(argc!=2 || sscanf(argv[1], "%d", &n) != 1 || n<2){
exit(-1);
}

int mx = 9*n + 1;

int a[mx], b[mx], c[mx], pos;

for(pos=0; pos<mx; pos++){
if(pos>0 && pos<10){
a[pos] = 1;
}
else{
a[pos] = 0;
}
if(pos<10){
b[pos] = 1;
}
else{
b[pos] = 0;
}
}

int m, p;
for(m=1; m<=n-1; m++){
for(pos=0; pos<mx; pos++){
int s = 0;
for(p=0; p<=pos; p++){
s += a[p]*b[pos-p];
}

c[pos] = s;
}

for(pos=0; pos<mx; pos++){
a[pos] = c[pos];
}
}

for(pos=1; pos<mx; pos++){
printf("%04d %010d\n", pos, a[pos]);
}

return 0;
}


-
Thank you, Marko Riedel! Thank you very much! – Aleksey Bykov Jan 15 '13 at 19:49