What's the number?

We can think of the solutions of this problem as numbers with $6$ digits, since they are between $1$ and $1,000,000.$ So we are searching the solutions from the following equation: $x+y+z+t+w+u=18.$ The total of solutions for this equation is: ${{23}\choose{18}}=33649.$

An example for this solution is:

$(0,0,1,3,5,9)$ , which is equivalent to the number: $1359$ .

Now we have to take out the solutions which contain digits from $10$ to $18$ . We have to choose one of the variables to be one of these numbers above, so we have $6$ options to set each of them. Now we have to multiply by $6$ the total of solutions from the following inequality: $x+y+z+t+w \leq 8.$ Now comes the trick : the number of solutions of this inequality is equivalent to the number of solutions from the following equation: $x+y+z+t+w+u=8.$ Notice that, by introducing an extra variable, you insert solutions from $0$ to $8$ , which is equivalent to the inequality above except by one variable.

The total of solutions from this equation is: ${{13}\choose{8}}=1287$

So the total of solutions we are searching for, is: $33649-6\times1287=33649-7722=\boxed{25927}.$

With using generating function, the 18-sum-six-digit number can be expressed by the coefficient of its 18-powered term. Because of each digit must be either $0$ to $9$ , and we are considering the six-digit number; the generating function then is $f(x)=(1+x+x^2+...+x^8+x^9)^6$ That is, $f(x)=(\frac{1-x^{10}}{1-x})^6$ which can be explicitly stated as $f(x)=(1+\sum^{6}_{r=1}(-1)^rC_{6,r}x^{10r})(1+\sum_{r=1}^{\infty}C_{r+6-1,r}x^r)$ We eventually get the answer, i.e. the coefficient of 18-powered $x$ term, equal to $C_{23,18}-6*C_{13,8}=25927$

Lazy Pythonic approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def digit_sum(x):
    total = 0
    for digit in str(x):
        total += int(digit)
    return total
a = 1
count = 0
while a <= 1000000:
    if digit_sum(a) == 18:
        count += 1
    a += 1
print count

we have to consider integers less than 999,999.I will here take an example like 230661.This number satisfies the criteria that is sum of digits is 18.Now I will represent this integer as a notation of D's and s.Put number of D's corresponding to value of digit separated by stars which will mean spaces. So 230961=DD DDD *DDDDDD DDDDDD D.Now what I have to do now is arrange these Ds and stars.Total arrangement=23c5.There will be some bad integers where number of consecutive Ds will be 10 or more,because there is no digit as 10.So I will minus these cases which will be 6 13c5 . So numbers=23c5-6*13c5

int sum(int n){ int x=0; while(n){ x+=n%10; n/=10; } return x; } int main(){ int x=0; for(int i = 99;i<1000000;i++){ if(sum(i)==18){ x++; } } cout<<x; }