Well, I've been almost losing my mind over this one.

The question is: How many integers on the interval $[3000, 8000]$ have a digit sum of 20?

Well, the first thing I did was separating to groups according to the first digit. and then:

3- A+B+C=17

4- A+B+C=16

5- A+B+C=15

6- A+B+C=14

7- A+B+C=13

Now my main problem is: Since A, B, and C are digits, it means that they are on the interval $[0, 9]$. How do I take that restriction into account?

  • 1
    $\begingroup$ If A is 0, B needs to be atleast 4; if A is 1; B must be greater than 3 and you get the combinations. $\endgroup$
    – hjpotter92
    Mar 24, 2013 at 15:46
  • $\begingroup$ It still didn't answer how do you take all the rest of the restrictions into account. $\endgroup$ Mar 24, 2013 at 16:10
  • $\begingroup$ Since you already grouped them from 3k to 8k; group a little more? $\endgroup$
    – hjpotter92
    Mar 24, 2013 at 16:12
  • $\begingroup$ So the best way is just counting my way out? Sounds... Inefficient. $\endgroup$ Mar 24, 2013 at 16:31
  • $\begingroup$ @TheAlchemist Inefficient this! Count[Total[IntegerDigits[#]] & /@ Range[3000, 8000], 20] *karate chop* $\endgroup$
    – amr
    Mar 24, 2013 at 18:21

1 Answer 1


Method 1: Using generating functions, you want the coefficient of $x^{20}$ in $$(x^3+x^4+ \ldots +x^7)(1+x+ \ldots +x^9)^3=\frac{x^3(1-x^5)(1-x^{10})^3}{(1-x)^4}$$

Equivalently, we drop the $x^3$ factor and look for the coefficient of $x^{17}$.

We have $(1-x)^{-4}=\sum_{i=0}^{\infty}{\binom{i+3}{3}x^i}$. Expanding $(1-x^5)(1-x^{10})^3$ and ignoring $x^n, n>17$ gives $(1-x^5)(1-3x^{10})=1-x^5-3x^{10}+3x^{15}$.

Finally the coefficient of $x^{17}$ is $$\binom{(17-0)+3}{3}-\binom{(17-5)+3}{3}-3\binom{(17-10)+3}{3}+3\binom{(17-15)+3}{3}$$

which easily evaluates to give $355$.

Method 2: As you might not be familiar with generating functions, here is a more elementary approach.

We proceed exactly as you did. If the 1st digit is $i$, then we have $A+B+C=20-i$. This gives $\binom{(20-i)+2}{2}$, but we have also counted those where $A, B, C$ are $\geq 10$. For those cases, exactly 1 of the digits is $\geq 10$. If it is $A$, we have $A=k=10, 11, \ldots , 20-i$. Then $B+C=20-i-k$, giving $21-i-k$ ways. The number of ways for $B, C$ are the same. Therefore we must subtract $3\sum\limits_{k=10}^{20-i}{(21-i-k)}=3\sum\limits_{j=1}^{11-i}{j}=3\frac{(11-i)(12-i)}{2}$.

Therefore the total number is


  • $\begingroup$ Well, This is the best answer i could possibly get, Thank you. $\endgroup$ Mar 24, 2013 at 21:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .