Re: counting how many positive integers <n have digits that add up to m
 From: KaiUwe 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 (((1x^10)/(1x))^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 (1x^10)/(1x) 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 mth coefficient of
p(x)^k. Nice.
Best
KaiUwe 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
 counting how many positive integers <n have digits that add up to m
 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):
Relevant Pages
