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

• From: S Perryman <a@xxxxx>
• Date: Sun, 23 May 2010 12:54:09 +0100

superpollo wrote:

S Perryman ha scritto:

Daniel T. wrote:

My first thought is that there might be a formula that will return the result with no loops.

My first reply to you is :

What formula are you offering for computing the desired result .... ??

maybe some generating function magic ?

m=10, n = 12345 :

Smallest number is 19.
Break into 1 | 9.
There are (9 - 1) + 1 numbers < 100 (19, 28, ... 91) .

Somehow compute the next number.
x = 109 (19 + 90) .
Break into 10 | 9. Break into (10 mod 10) | 9 = 0 | 9.
There are (9 - 0) + 1 = 10 numbers < 200 (109, 118, ... 190) .

Compute the next number.
x = 208 (109 + 99) .
Break into 20 | 8. Break into (20 mod 10) | 8 = 0 | 8
There are (8 - 0) + 1 = 9 numbers less in 300.

And so on.

So there are variant conditions as to when to add 90 or 99 to
get the start of the next block of numbers.

But there are also some deviant cases. :-(
For example : x = 901.

Meaning 9 | 1.
1 - 9 + 1 does not equal 2 (901, 910) .

The next number is 1009.
901 + 90 = 991. 901 + 99 = 1000. Both are wrong.

However, 910 (the last number in the block) + 99 = 1009.

Regards,
Steven Perryman
.

• References: