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

Question

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!

Answer 1

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.

Answer 2

Try assembling the digits from the number.

Answer 3

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.

Answer 4

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){
    fprintf(stderr, "single numeric argument please");
    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;
}