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

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
.

Relevant Pages