counting how many positive integers <n have digits that add up to m
superpollo
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?
bye
Kai-Uwe Bux
Looks a little slow. Maybe something along the following lines is faster for
larger n. I will describe the method using an example: n = 2763 and m = 16.
First, all numbers of the form
0xxx, sum of x = 16 : 69 possibilities
1xxx, sum of x = 15 : 73 possibilities
qualify. Now, you also have
20xx, sum of x = 14 : 5 possibilities
21xx, sum of x = 13 : 6 possibilities
...
26xx, sum of x = 8 : 9 possibilities
270x, x = 7 : 1
271x, x = 6 : 1
...
275x, x = 2 : 1
and 2763 does not qualify. Total: 167 (maybe, I did many calculations on
paper:-)
What this shows is that a subroutine computing
the number of k-digit numbers whose digits sum up to m
would be good. For three digits xxx, sum of x = 16, one could do:
970 : 6 permutations (also 907, 790, 709, 097, 079)
961 : 6 permutations
952 : 6 permutations
943 : 6 permutations
880 : 3 permutations
871 : 6 "
862 : 6 "
853 : 6 "
844 : 3 "
772 : 3 "
763 : 6 "
754 : 6 "
664 : 3 "
655 : 3 "
total: 6*9 + 3*5 = 69.
That one can compute the result for n=2763, m=16 without testing 2763
numbers goes to show that there is room for improvement.
Best
Kai-Uwe Bux
S Perryman
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
robin
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;
Willem
) 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:
) 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
Willem
) "superpollo" <ute...@esempio.net> wrote in message news:4bf44372$0$31380$4faf...@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)):
)| if sum == m:
)| 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 ?
S Perryman
> 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
superpollo
it will take me some time to read the messages carefully.
meanwhile, thanks a lot!
bye
superpollo
> 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.
Willem
) 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.
robin
| robin wrote:
| ) "superpollo" <ute...@esempio.net> wrote in message news:4bf44372$0$31380$4faf...@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.
Daniel T.
My first thought is that there might be a formula that will return the
result with no loops.
Lie Ryan
This is a partitioning/distribution problem.
Given:
u1 + u2 + u3 + ... + uN = M
with restrictions 0 <= uX <= 9 for all X in {1..N}
You can solve this problem with some combinatorics magic.
Let C(n, r) be Combination function (i.e. (n!) / ((n-r)!(r)!)) then
The number of possible ways to Partition/Distribute M items over N
buckets is given by:
D(M, N) = C(M + N - 1, M)
[*] for why the formula works, see below
Using the same example as Kai-Uwe Bux, if we want to solve how many 3
digit number (i.e. < 1000) have digits that add up to 16, we can have:
u1 + u2 + u3 = 16 ; 0 <= uX <= 9 for all X in {1, 2, 3}
that means
M = 16
N = 3 // there are u1,u2,u3 so 3 buckets
I1: D(16, 3) = C(16 + 3 - 1, 16) = 153
Therefore, there are 153 ways to distribute 16 items over 3 bucket.
However, we have not put any restrictions on uX,
the calculations we did includes cases where the "digits" can be greater
than 9, e.g. u1 = 14
so we need to exclude the cases where u1 >= 10.
let v1 = u1 + 10
u1 + u2 + u3 = 16
v1 + 10 + u2 + u3 = 16
v1 + u2 + u3 = 6
now we need to distribute 6 items over another 3 buckets (v1, u2, u3),
using the distribution formula:
X1: D(6, 3) = C(6 + 3 - 1, 6) = 28
also, we need to exclude the cases where u2 >= 10 and u3 >= 10
by using similar argument as when u1 >= 10:
X2: D(6, 3) = 28
X3: D(6, 3) = 28
in this particular case, we couldn't have double-excluded anything so we
don't need to include any more things using Principle of
Inclusion-Exclusion (read on this later, it's an important principle on
how the counting works).
Therefore:
I1 - (X1 + X2 + X3) = 153 - (28 * 3) = 69
Now, the method above as is only works when the limit N is a multiple of
10 (e.g. N == {10, 100, 1000, ...}). But it isn't that difficult to
extend it so that it works when N is arbitrary number.
Appendix A:
why does the distribution formula works?
Consider distributing 3 items over 3 buckets:
| |*** = 3
| *| ** = 21
*| | ** = 12
| **| * = 21
*| *| * = 111
**| | * = 201
|***| = 30
*| **| = 120
**| *| = 210
***| | = 300
which can be rewritten as:
||*** = 3
|*|** = 21
*||** = 12
|**|* = 21
*|*|* = 111
**||* = 201
|***| = 30
*|**| = 120
**|*| = 210
***|| = 300
this happens to be the equivalent as the problem of choosing the
Combination of 5 items (3 *s and 2 |s); therefore we can use the
combination formula: C(3 + 2, 3) == C(3 + 3 - 1, 3)
Appendix B:
def fact(n):
""" factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """
p = 1
for i in range(1,n+1):
p *= i
return p
def C(n, r):
""" regular Combination (nCr)
return fact(n) / (fact(n - r) * fact(r))
def D(M, N):
""" Distribution aka Partitioning """
return C(M + N - 1, M)
superpollo
i'll print and frame.
thanks
Kai-Uwe Bux
I like that. Here is an alternative account that does not overcount and
hence does not use inclusion exclusion.
The idea is as follows: first, choose the positions of the 9s. You can put,
k = 0, 1, ... m/9 of them. For each value k, you have (n choose k)
placements and in the remaining n-k slots, you get to put the digits
0,1,...,8 with total sum m - k*9. That suggests a recursion:
N(m,n,b) := number of n-digit strings in base b with digit sum m.
N(m,n,b) = ( n choose m ) if b = 2
N(m,n,b) = sum_{k=0}^{m/(b-1)} ( n choose k ) * N( m-(b-1)*k, n-k, b-1 )
> Therefore:
>
> I1 - (X1 + X2 + X3) = 153 - (28 * 3) = 69
>
Admittedly, N(m,n,b) involves more terms even for this example, but is very
easy to implement and still a vast improvement over checking each candidate.
I have to think about inclusion/exclusion a bit more.
[...]
Best
Kai-Uwe Bux
S Perryman
> 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
S Perryman
> superpollo <ute...@esempio.net> wrote:
>>in python:
>>any suggestion for improvement?
My first reply to you is :
What formula are you offering for computing the desired result .... ??
Regards,
Steven Perryman
superpollo
maybe some generating function magic ?
Willem
) 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.
S Perryman
> S Perryman ha scritto:
>> Daniel T. wrote:
m=10, n = 12345 :
Smallest number is 19.
Break into 1 | 9.
There are (9 - 1) + 1 numbers < 100 (19, 28, ... 91) .
Somehow compute the next number.
x = 109 (19 + 90) .
Break into 10 | 9. Break into (10 mod 10) | 9 = 0 | 9.
There are (9 - 0) + 1 = 10 numbers < 200 (109, 118, ... 190) .
Compute the next number.
x = 208 (109 + 99) .
Break into 20 | 8. Break into (20 mod 10) | 8 = 0 | 8
There are (8 - 0) + 1 = 9 numbers less in 300.
And so on.
So there are variant conditions as to when to add 90 or 99 to
get the start of the next block of numbers.
But there are also some deviant cases. :-(
For example : x = 901.
Meaning 9 | 1.
1 - 9 + 1 does not equal 2 (901, 910) .
The next number is 1009.
901 + 90 = 991. 901 + 99 = 1000. Both are wrong.
However, 910 (the last number in the block) + 99 = 1009.
Regards,
Steven Perryman
Daniel T.
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'.)
S Perryman
> S Perryman <a...@a.net> wrote:
>>Daniel T. wrote:
>>>My first thought is that there might be a formula that will return the
>>>result with no loops.
>>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.
I feel there is not an exact formula as such, in the manner of something
like the sum of all squares etc.
Although computing the first number that meets the criteria is
universally ok, as is calculating the 'delta' between successive numbers in
a 'block' of such numbers, for me tis the non-obvious univeral means at the
moment of identifying the start number (see my other posts) in each
block based on info inherent on previous blocks, that is the issue for me
regarding the possibility of such a formula.
Regards,
Steven Perryman
superpollo
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
^^^^^^
bye
Kai-Uwe Bux
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
Kai-Uwe Bux
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
Lie Ryan
> This is a partitioning/distribution problem.
>
> Given:
> u1 + u2 + u3 + ... + uN = M
> with restrictions 0 <= uX <= 9 for all X in {1..N}
>
> You can solve this problem with some combinatorics magic.
>
>
>
> Let C(n, r) be Combination function (i.e. (n!) / ((n-r)!(r)!)) then
>
> The number of possible ways to Partition/Distribute M items over N
> buckets is given by:
>
> D(M, N) = C(M + N - 1, M)
>
more combinatoric magic.
Assuming N == 10**i for some integer i (i.e. N is one of {10, 100, 1000,
10000, ...}).
For example, when calculating prttn(32, 10000) then:
u1 + u2 + u3 + u4 = 32
inclusion (no rule): D(32, 4) * C(4, 0)
exclusion (1 rule): D(22, 4) * C(4, 1)
inclusion (2 rules): D(12, 4) * C(4, 2)
exclusion (3 rules): D( 2, 4) * C(4, 3)
inclusion (4 rules): D(-8, 4) * C(4, 4)
[*] why this works? see Appendix C
>>> D(32, 4) * C(4, 0) - D(22, 4) * C(4, 1) + D(12, 4) * C(4, 2) - D( 2,
4) * C(4, 3) + D( -8, 4) * C(4, 4)
35L
>>> prttn(32, 10000)
35
knowing how to deal when N in {10, 100, 1000, ...}, we have an easy way
to deal when N is a*(10**i)
Appendix B.2:
# memoizing might help a lot here
def fact(n):
""" factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """
p = 1
for i in range(1,n+1):
p *= i
return p
def C(n, r):
""" regular Combination (nCr) """
return fact(n) / (fact(n - r) * fact(r))
def D(M, N):
""" Distribution aka Partitioning """
return C(M + N - 1, M)
def partition10(M, i):
""" Count how many integer < N sums to M where N = 10**int(i) """
s = 0
sign = 1
for j in range(i + 1):
s += sign * D(M, i) * C(i, j)
# flip the sign for inclusion-exclusion
sign *= -1
# if M = 32, then 32, 22, 12, 2, -8
M -= 10
return s
Appendix C:
when we apply no rule for inclusion (i.e. uX can range freely between
{0..32}):
u1 + u2 + u3 + u4 = 32
D(32, 4)
{there is C(4, 0) == 1 possibilities}
then when we applying 1 rule for exclusion (i.e. at least one of {0 <=
u1 < 10, 0 <= u4 < 10, 0 <= u4 < 10, 0 <= u4 < 10} is true):
v1 + u2 + u3 + u4 = 22
u1 + v2 + u3 + u4 = 22
u1 + u2 + v3 + u4 = 22
u1 + u2 + u3 + v4 = 22
{there is C(4, 1) == 4 possibilities}
then when we are applying 2 rules for inclusion (i.e. at least two of {0
<= u1 < 10, 0 <= u4 < 10, 0 <= u4 < 10, 0 <= u4 < 10} is true):
v1 + v2 + u3 + u4 = 12
v1 + u2 + v3 + u4 = 12
v1 + u2 + u3 + v4 = 12
u1 + v2 + v3 + u4 = 12
u1 + v2 + u3 + v4 = 12
u1 + u2 + v3 + v4 = 12
{there is C(4, 2) == 6 possibilities}
{note that enumerating this is equivalent to choosing two uX out of four
to be turned into two vX}
then when we are applying 3 rules for inclusion (i.e. at least three of
{0 <= u1 < 10, 0 <= u4 < 10, 0 <= u4 < 10, 0 <= u4 < 10} is true):
v1 + v2 + v3 + u4 = 2
v1 + v2 + u3 + v4 = 2
v1 + u2 + v3 + v4 = 2
u1 + v2 + v3 + v4 = 2
{there is C(4, 3) == 4 possibilities}
{note that enumerating this is equivalent to choosing three uX out of
four to be turned into three vX}
then when we are applying 4 rules for inclusion (i.e. all for of {0 <=
u1 < 10, 0 <= u4 < 10, 0 <= u4 < 10, 0 <= u4 < 10} is true):
v1 + v2 + v3 + v4 = -8
{there is C(4, 4) == 1 possibilities}
{note that D(-8, 4} == 0, so this is only included for algorithm
completeness}