Re: counting how many positive integers <n have digits that add up to m

superpollo wrote:
) in python:
)
) def prttn(m, n):
) tot = 0
) for i in range(n):
) s = str(i)
) sum = 0
) for j in range(len(s)):
) sum += int(s[j])
) if sum == m:
) tot += 1
) return tot
)
) any suggestion for improvement?

Yes, several.

First of all, take a look at the pattern of differences between consecutive
numbers and their digit sums: It's always +1, except for a rollover where
you get -8, -17, -26, -35, etc.
IOW: It's +1, -9*(number of rollovers)

Second, note that 9 out of 10 times, you get the +1, so you can basically
make steps of 10 as long as you're not near the target sum.

Third, if you are near the target sum, you can basically work out at
once how many steps you need to take to find the number.

Fourth, there is no need to work out exactly which is the number that
matches the sum, as long as you know there is one so you can count it.

IOW: You can make steps of 10, and at each step check if the target sum is
within reach of the next 10 numbers (if the difference is less than 10).

Fifth, you're now making steps of 10, but 9 out of 10 times that amounts
to making a +1 step. If you're not near the target sum, that means that
you can do 10 of those steps at once.

Sixth, if you are near the target sum, then you can basically work out
how many times the sum will be hit in a block of 100: It's at most 10
times, and that's when the target sum is exactly 9 more than the current
sum. If the difference to the target sum is greater or smaller, then
there are that many less hits in the block.
(There are 10 numbers <100 with a digit sum of 9)
(There are 9 numbers <100 with a digit sum of 8 or 10)
(There are 8 numbers <100 with a digit sum of 7 or 11)

Seventh, do you smell recursion here ? I sure do.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.