Count the integers from 1 to 10^6 whose decimal digits sum to exactly 12. Give the number and a digit dynamic programming or generating function derivation.

Count the integers from 1 to 10^6 whose decimal digits sum to exactly 12. Give the number and a digit dynamic programming or generating function derivation.

Approach: Treat the range as all six-digit strings with leading zeros allowed, then count solutions of a bounded sum with inclusion-exclusion or with a digit by digit table.

6062. Every integer from 0 to 999999 is a six-digit string with leading zeros allowed, so the count is the number of solutions of d_1 + ... + d_6 = 12 with 0 <= d_i <= 9. Stars and bars gives C(12 + 5, 5) = C(17,5) = 6188 solutions without the upper bound, and inclusion exclusion subtracts the cases where one digit exceeds 9: fixing d_i >= 10 leaves a sum of 2 across six digits, which is C(7,5) = 21 solutions, and there are 6 choices of which digit overflows, so 6188 - 126 = 6062. No two digits can both exceed 9 when the total is 12, so the alternating series stops there. Neither 0 nor 10^6 has digit sum 12, so the count on [1, 10^6] is the same 6062. The digit dynamic programming version carries the state (position, running sum, tight prefix flag), where the tight flag records whether the prefix built so far equals the prefix of the bound, and it runs in O(digits * sum * 10).

Follow-up: How many integers below 10^6 have digit sum 12 and are also divisible by 3, and why is that count easy?

Key concepts: digit dynamic programming, inclusion exclusion, stars and bars, tight prefix.