Prev: WinMenus version 1.0 ...
Next: counting how many positive integers <n have digits that add up to m
From: S Perryman on 21 May 2010 10:25
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?


m=10, n = 12350

s = [1,2,3,5,0]


1. Determine what numbers can exist.

No number can be formed if m > digit n + (9 * (s.size - 1) )

If m>37, the total = 0.


2. Get a fast fix on an upper bound for candidate numbers.

(q,r) = divide(m,s.size) = (2,0)

This means that c = 22222 ( [2,2,2,2,2] ) is a candidate.
Use c. c > n
Change c to 13222. c > n
Change c to 12322. c <= n. Got one.
Change c to 12331.
Change c to 12340.

Now you can mess around with c to get other values (3340, 12250 etc) .


Regards,
Steven Perryman
From: Willem on 21 May 2010 10:55
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)

Second, note that 9 out of 10 times, you get the +1, so you can basically
make steps of 10 as long as you're not near the target sum.

Third, if you are near the target sum, you can basically work out at
once how many steps you need to take to find the number.

Fourth, there is no need to work out exactly which is the number that
matches the sum, as long as you know there is one so you can count it.

IOW: You can make steps of 10, and at each step check if the target sum is
within reach of the next 10 numbers (if the difference is less than 10).

Fifth, you're now making steps of 10, but 9 out of 10 times that amounts
to making a +1 step. If you're not near the target sum, that means that
you can do 10 of those steps at once.

Sixth, if you are near the target sum, then you can basically work out
how many times the sum will be hit in a block of 100: It's at most 10
times, and that's when the target sum is exactly 9 more than the current
sum. If the difference to the target sum is greater or smaller, then
there are that many less hits in the block.
(There are 10 numbers <100 with a digit sum of 9)
(There are 9 numbers <100 with a digit sum of 8 or 10)
(There are 8 numbers <100 with a digit sum of 7 or 11)

Seventh, do you smell recursion here ? I sure do.


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: Willem on 21 May 2010 11:04
robin wrote:
) "superpollo" <utente(a)esempio.net> wrote in message news:4bf44372$0$31380$4fafbaef(a)reader1.news.tin.it...
)| 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?
)
) Looks like your code finds the number of integers <= n, not < n.
)
) There are three loops in your code, one of which is implied.

Where ? I don't see it.
Or do you mean the number-to-string conversion ?


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 21 May 2010 11:38
S Perryman wrote:

> m=10, n = 12350

> s = [1,2,3,5,0]

> 1. Determine what numbers can exist.

> No number can be formed if m > digit n + (9 * (s.size - 1) )

> If m>37, the total = 0.

What a load of rubbish (embarrassed :-( ) .
The largest number < n with the biggest digit sum would be
11999. Which requires m <= 29.


Regards
From: superpollo on 21 May 2010 11:38
many thanks to all who cared to answer.

it will take me some time to read the messages carefully.

meanwhile, thanks a lot!

bye

 |  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