Prev: counting how many positive integers <n have digits that add upto m
Next: complexity again. (was: on goto)
From: robin on 21 May 2010 10:41
"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.

The following PL/I code uses two loops :-

sumdigs: procedure (m, n) returns (fixed binary (31));
declare (m, n) fixed binary (31);
declare (tally initial (0), i, k, sum) fixed binary (31);

do i = 1 to n;
k = i; sum = 0;
do while (k > 0); /* Sums the digits of the integer I. */
sum = sum + mod(k, 10);
k = k / 10;
end;
if sum = m then tally = tally + 1;
end;
return (tally);
end sumdigs;


From: robin on 21 May 2010 21:15
"Willem" <willem(a)turtle.stack.nl> wrote in message news:slrnhvd87i.h39.willem(a)turtle.stack.nl...
| 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.

I did say that it was "implied".

| Or do you mean the number-to-string conversion ?

The number-to-string conversion is the implied loop.


From: Daniel T. on 22 May 2010 08:47
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.
From: Daniel T. on 23 May 2010 12:36
S Perryman <a(a)a.net> wrote:
> 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 .... ??

I spent a few minutes (maybe as many as 30) on this question. Like I
said, my feeling is that there is a formula for this, but my math skills
are not up to the task. For example, any such formula would have to be
able to determine the base 10 magnitude of 'n' and I'm not sure how to
do that (although I think it is possible using a formula.) Once that is
found, then a curve formula can show the count for any particular value
on the curve, similar to computing dice probabilities (with the number
of 10 sided dice equal to the magnitude of 'n'.)
From: Kai-Uwe Bux on 23 May 2010 17:49
Willem wrote:

> Willem wrote:
> ) This is absolute peanuts compared to some of the other things I
> mentioned.
>
> Here's a setup to a simple recursive solution:
>
> - The function cnt(m, x) equals the number of integers lower than 10^x
> with a digit sum equal to m.
>
> (To get the count for arbitrary n, you need a second function, that
> divides up n into its digits and then calculates for each digit.)
>
> The base is easy:
>
> - cnt(m, 0) :=
> 1 if m == 0
> 0 otherwise
>
> Now here's the really nice bit:
> If you can calculate how many hits there are in a set of, say, 100
> numbers, then you can use that to calculate the number of hits in a set of
> 1000
> numbers. You see, the number of hits in, say, the range 800-899 is equal
> to the number of hits in 00-99 for a target that is 8 less.
>
> Or, more precisely:
> - cnt(m, x) :=
> sum (0 <= i <= 9) { cnt(m - i, x-1) }
>
> Now, if you apply this blindly, you still end up doing N calculations.
> But you might notice that you're doing the same calculation a lot of
> times. So if you store those calculations, it will go a lot faster.
>
> You can do this bottom-up, if you keep a table. You just need to figure
> out the minimum and maximum number of m that needs calculating.
>
> The start of the table would be something like:
>
> 1
> 1 1 1 1 1 1 1 1 1 1
> 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1
> 1 3 6 10 15 21 28 36 45 55 63 69 73 75 75 73 69 63 55 45 36 28 21 15 ...
>
> The first column is for m=0, the first row is for x=0 (or n=1)
> Basically, each cell in the table is the sum of the 10 cells in
> the row above it, ending on the same column.
>
> (For example, there are 75 numbers < 1000 with a digit sum of 14)
>
> So you need a maximal width of the target m you're looking for,
> and a height of the number of digits in n.
>
>
> Of course, with this you won't find the actual numbers, just the count.

Wow, that is really fast.

The following does not even try to guess to what extend the table needs to
be filled. It just caches values already computed.

#include <map>
#include <utility>
#include <cassert>
#include <iostream>
#include <ostream>

unsigned long long cnt ( unsigned m,
unsigned x ) {
// # of integers in [0, 10^x) whose digits sum up to m
typedef unsigned long long result_type;

if ( x == 0 ) {
return ( m == 0 ? 1ul : 0ul );
}
if ( m > 9*x ) {
return ( 0ul );
}

typedef std::pair< unsigned, unsigned > arguments;
typedef std::map< arguments, result_type > cache;
static cache the_cache;
arguments the_args ( m, x );
cache::iterator iter = the_cache.find( the_args );
if ( iter != the_cache.end() ) {
return ( iter->second );
}

result_type a = cnt( m, x-1 );
result_type b = m > 0 ? cnt( m-1, x ) : 0u;
result_type c = m >= 10 ? cnt( m - 10, x-1 ) : 0u;

result_type result = a + b - c;

the_cache[ the_args ] = result;

return ( result );
}

int main ( void ) {
for ( unsigned int x = 0; x < 15; ++x ) {
for ( unsigned int m = 0; m <= x*9; ++m ) {
std::cout << "#digits = " << x
<< ", sum = " << m
<< " : " << cnt( m, x ) << "\n";
}
std::cout << "\n";
}
}


Best

Kai-Uwe Bux
 |  Next  |  Last
Pages: 1 2
Prev: counting how many positive integers <n have digits that add upto m
Next: complexity again. (was: on goto)