Dedicated to Swapnil Das

Since $10^{6}$ has a digit sum of $1,$ we can look at the set of six-digit "numbers" $\overline{abcdef}$ for integers $0 \le a,b,c,d,e,f \le 9.$ With this formatting, the integer $102,$ for example, is represented by the six-digit "number" $000102,$ and in fact there is a one-to-one correspondence between these six-digit "numbers" and the integers between $1$ and $10^{6}.$ ( $1 \equiv 000001$ has a digit sum of $1$ so it is not of importance that it is included in this formatting.)

The number of integer solutions we are looking for are then the number of solutions to the equation

$a + b + c + d + e + f = 15, 0 \le a,b,c,d,e,f \le 9 ,$ ... (A).

Now look at the companion equation $a' + b' + c' + d' + e' + f' = 15$ with $0 \le a',b',c',d',e',f' \le 15$ , ...(A'). This is a "stars and bars" equation, and thus has $\dbinom{15 + 6 - 1}{6 - 1} = \dbinom{20}{5}$ solutions. The difference between equations (A) and (A') is the range of possible values for the variables, with the effect that any solution for (A') which involves any of its variables having a value of $10$ or more will not be a solution for (A). So to find the number of solutions to (A) we need to subtract from $\dbinom{20}{5}$ those solutions of (A') that involve variables taking on a value of $10$ or more.

Now we can only have one of $a',b',c',d',e',f'$ be $10$ or more in a given solution to (A'), since then the greatest value any other variable could have is $15 - 10 = 5.$ So we can look at the number of solutions with $a'$ equalling, in turn, $10,11,12,13,14,15$ , and then multiply by $6,$ (to account for those solutions that have each of $b',c',d',e',f'$ take on these values, (all mutually exclusive)), to find the number of solutions to (A') that are not also solutions to (A).

In general, with $a' = 10 + k, 0 \le k \le 5,$ we then have the associated equation

$b' + c' + d' + e' + f' = 5 - k$ with $0 \le b',c',d',e',f' \le 5 - k$

to solve. As these are "stars and bars" equations we know that in general there are

$\dbinom{(5 - k) + 5 - 1}{5 - 1} = \dbinom{9 - k}{4}$ associated solutions. So the number of solutions to (A) is

$\dbinom{20}{5} - 6*\displaystyle\sum_{k=0}^{5} \dbinom{9 - k}{4} = \dbinom{20}{5} - 6*\left(\dbinom{9}{4} + \dbinom{8}{4} + \dbinom{7}{4} + \dbinom{6}{4} + \dbinom{5}{4} + \dbinom{4}{4}\right) =$

$15504 - 6*(126 + 70 + 35 + 15 + 5 + 1) = 15504 - 6*252 = \boxed{13992}$ solutions.

(Note that we can simplify the calculation by employing the hockey stick identity

$\displaystyle\sum_{i=r}^{n} \dbinom{i}{r} = \dbinom{n + 1}{r + 1}$ where $n \gt r.$

Then $\displaystyle\sum_{k=0}^{5} \dbinom{9 - k}{4} = \sum_{i=4}^{9} \dbinom{i}{r} = \dbinom{9 + 1}{4 + 1} = \dbinom{10}{5}.$

Thus our calculation can be simplified to $\dbinom{20}{5} - 6*\dbinom{10}{5} = 15504 - 6*252 = 13992$ as before.)

Here is my C++ code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>
using namespace std;

int main() {
    int num, sum, count = 0;    
    for (int i = 1; i <= 1000000; i++) {
        num = i; sum = 0;
        while (num != 0) {
              sum = sum + num % 10;
              num = num / 10;
        }
        if (sum == 15) count++;
    }
    cout << count;
    return 0;
}

And the output is:

1

13992