Prev: WinMenus version 1.0 ...
Next: counting how many positive integers <n have digits that add up to m
From: superpollo on 21 May 2010 11:39
Willem ha scritto:
> superpollo 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?
>
> Yes, several.
>
> First of all, take a look at the pattern of differences between consecutive
> numbers and their digit sums: It's always +1, except for a rollover where
> you get -8, -17, -26, -35, etc.
> IOW: It's +1, -9*(number of rollovers)

this is a very useful optimization.
From: Willem on 21 May 2010 11:49
superpollo wrote:
) Willem ha scritto:
)> Yes, several.
)>
)> First of all, take a look at the pattern of differences between consecutive
)> numbers and their digit sums: It's always +1, except for a rollover where
)> you get -8, -17, -26, -35, etc.
)> IOW: It's +1, -9*(number of rollovers)
)
) this is a very useful optimization.

This is absolute peanuts compared to some of the other things I mentioned.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
From: S Perryman on 23 May 2010 05:47
Willem wrote:
> superpollo 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?
>
> Yes, several.
>
> First of all, take a look at the pattern of differences between consecutive
> numbers and their digit sums: It's always +1, except for a rollover where
> you get -8, -17, -26, -35, etc.
> IOW: It's +1, -9*(number of rollovers)

A related idea came to me. For example : m = 10, n = 12345.

Find the smallest number equal to m.
That number can be found by : 9 + (10 -9) * 10 = 19.

1. Start with 19. Add a delta value (d) . Here d is 9.
19 + 9 = 28. 28 + 9 = 37. ... 82 + 9 = 91.

If you consider 19 as a tuple (x,y) then you effectively have a loop
where x is increasing by 1 and y is decreasing by 1.

The loop terminates when x = 9 or y = 0.


2. So what is the next candidate number from 91 ??
You add an increment (incr) .
The value of incr is 90 whenever the smallest possible number > 9.
Otherwise the value is 99.

Then repeat the loop defined in #1.


So you get two loops.
The outer loop adjusts by incr.
The inner loop adjusts by d.

The values of d and incr are powers of 10 dependent on the number of digits
in the smallest number.

m = 20, smallest number = 299.
d = 90. incr = 900.

The larger the value of m, the bigger d and incr will become, and the
faster the loop will be.


3. Unfortunately, my '15 minute analysis' did not reveal an obvious
terminating condition for the case when all possible numbers <= n have
been found (exercise for the reader ?? :-) ) .


Regards,
Steven Perryman
From: S Perryman on 23 May 2010 05:54
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 .... ??


Regards,
Steven Perryman
From: superpollo on 23 May 2010 06:26
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 ?
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: WinMenus version 1.0 ...
Next: counting how many positive integers <n have digits that add up to m