Prev: counting how many positive integers <n have digits that add upto m
Next: complexity again. (was: on goto)
From: Kai-Uwe Bux on 23 May 2010 18:23
superpollo wrote:

> superpollo ha scritto:
>> S Perryman ha scritto:
>>> Daniel T. wrote:
>>>
>>>> superpollo <utente(a)esempio.net> 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
First  |  Prev  | 
Pages: 1 2
Prev: counting how many positive integers <n have digits that add upto m
Next: complexity again. (was: on goto)