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

*From*: Kai-Uwe Bux <jkherciueh@xxxxxxx>*Date*: Mon, 24 May 2010 00:23:07 +0200

superpollo wrote:

superpollo ha scritto:

S Perryman ha scritto:

Daniel T. wrote:

superpollo <utente@xxxxxxxxxxx> 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?

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 ?

like this:

(%i12) taylor (((1-x^10)/(1-x))^7, x, 0, 31);

(%o12)

1+7*x+28*x^2+84*x^3+210*x^4+462*x^5+924*x^6+1716*x^7+3003*x^8+5005*x^9

+8001*x^10+12327*x^11+18368*x^12+26544*x^13+37290*x^14+51030*x^15

+68145*x^16+88935*x^17+113575*x^18+142065*x^19+174195*x^20+209525*x^21

+247380*x^22+286860*x^23+326865*x^24+366135*x^25+403305*x^26

+436975*x^27+465795*x^28+488565*x^29+504315*x^30+512365*x^31

^^^^^^

That takes the word "magic" too literally :-)

The function (1-x^10)/(1-x) is a polynomial:

p(x) := 1 + x + x^2 + ... + x^9

and raising that to powers leads to polynomials whose coefficients form the

generalized Pascal triangle which the post from Willem mentions. It's

exactly that multiplying a polynomial by p(x) adds chunks of 10 consecutive

coefficients.

So, indeed, the function cnt(m,k) can be regarded as the m-th coefficient of

p(x)^k. Nice.

Best

Kai-Uwe Bux

.

**References**:**counting how many positive integers <n have digits that add up to m***From:*superpollo

**Re: counting how many positive integers <n have digits that add up to m***From:*Daniel T.

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

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

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

- Prev by Date:
**Re: counting how many positive integers <n have digits that add up to m** - Next by Date:
**Re: WinMenus version 1.0 ...** - Previous by thread:
**Re: counting how many positive integers <n have digits that add up to m** - Next by thread:
**Re: counting how many positive integers <n have digits that add up to m** - Index(es):