How many decimal integers below 10^20 exist having sum of their digits less than 4?
There are 3 1digit numbers 1,2,3
6 2digit numbers 10,11,12,20,21,30
10 3digit numbers 100,101,102,110,111,120,200,201,210,300
15 4digit numbers 1000,1001,1002,1010,1011,1020,1100,1101,1200,2000,2001,2010,2100
Based on this evidence I conjecture there are (n+1)*(n+2)/2 ndigit numbers of the desired type. If that's the case the answer is the sum of 3 + 6 + 10 + 15 +. . .+ 231.
Checking the differences I get the formula (n/6)*(n^2 + 6n + 11) with value = 1770 for n = 20. A quick run of the tape confirms.

Posted by xdog
on 20171106 17:33:56 