Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

4 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you for your answer, Henning Makholm! –  Alexey Jan 14 '13 at 21:31
add comment

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;
}

share|improve this answer
    
Thank you, Marko Riedel! Thank you very much! –  Alexey Jan 15 '13 at 19:49
add comment

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.

share|improve this answer
    
Thanks a lot for such a detailed answer, Marko Riedel! What you say is very important to me. Thank you! –  Alexey Jan 15 '13 at 0:51
add comment

Try assembling the digits from the number.

share|improve this answer
    
Thank you for your answer, Loki Clock! –  Alexey Jan 14 '13 at 21:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.