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);



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

So, indeed, the function cnt(m,k) can be regarded as the m-th coefficient of
p(x)^k. Nice.


Kai-Uwe Bux

Relevant Pages