Re: Help with a recursive equation

On Jul 3, 12:05?am, Proginoskes <CCHeck...@xxxxxxxxx> wrote:
On Jul 2, 12:37 am, "mensana...@xxxxxxxxxxx" <mensana...@xxxxxxx>
wrote:

On Jul 1, 10:14?pm, Proginoskes <CCHeck...@xxxxxxxxx> wrote:

On Jul 1, 12:19 am, "mensana...@xxxxxxxxxxx" <mensana...@xxxxxxx>
wrote:
A quick Maple check shows that the recurrence _is_ counting numbers
like 011, so you are correct on that point. However, this is only a
side issue, since the OP asked for the SUM of these numbers, not a
COUNT.

I know. I recognized that and corrected it before your
first post. Don't know why you're going on about it.
Perhaps you didn't read the whole thread?

I scanned it and then went back and replied to where I thought it was
appropriate.


If a number like 011 is allowed, then as you said, recursion isn't
necessary. (If you write the numbers in a column, every column has the
same number of 1's, and the sum is easy to calculate.*) It is only a
difficult problem if you don't allow leading 0's.

* For instance, to calculate S(3,2), write the C(3,2) numbers in a
column. The total number of 1's in this "matrix" is 2*C(3,2) (2 1's in
each row). Since each column has the same number of 1's in it, there
are exactly
2*C(3,2)/3 = C(2,1) 1's in each column. Thus, if we create a new
"matrix of binary numbers" with C(2,1) rows and 3 columns, and convert
them to numbers and add them together, we'll get S(3,2). But 3 1's in
a row is the binary form for (2^3 - 1), and we're multiplying by
C(2,1), so the answer is
(2^3 - 1) * C(2,1). (In general it will be (2^n - 1) * C(n-1, m-1), if
m,n >= 1.)

EXERCISE: What is the answer if you do NOT allow leading 0's in your
numbers?

Let's suppose that S*(n,m) is the sum of all n-bit binary numbers with
exactly m 1's and no leading 0's, and S(n,m) is the sum of all n-bit
binary numbers with exactly m 1's.

I don't get this. Are you saying that the binary pattern
1111 is being summed 5 times?

No. I'm saying that now S*(3,2) = 110 + 101 (binary), but S(3,2) = 110
+ 101 + 011.

Ok.


So if we exclude the patterns with leading 0's,
the sum would get smaller, right?

But when I run the check routine using popcount,
I know for a fact that 1111 is only counted once
(as 00001111), yet I get the same sum.

1111 would be counted by S*(4,4) but not by S*(8,4), since 00001111
has a leading 0. 1111 wouldn't be counted in S*(8,4), since it is not
an 8-bit number.

So it doesn't get counted at all. That's why the
result would be different.


Which must mean the OP's algorithm is effectively
not summing the numbers with leading 0's making
the answer to your question: no change whatsoever.

The answer to this is not as difficult as I thought at first:

S*(n,m) = S(n,m) - S(n-1, m),

import gmpy
def S(n,m):
if n==0 or m==0 or n<m:
return 0
else:
return S(n-1,m) + (2**(n-1))*gmpy.comb(n-1,m-1) + S(n-1,m-1)
print """
S(8,4) = %d
- S(7,4) = %d
-----------------
%d""" % (S(8,4),S(7,4),S(8,4)-S(7,4))


## S(8,4) = 8925
## - S(7,4) = 2540
## -----------------
## 6385

So you're summing only numbers that have exactly
8 bits with the MSB always 1 (nothing like the
OP's original problem, but it's your excercise).

s = []
for i in xrange(128,256): # bit 7 always 1
if gmpy.popcount(i)==4:
s.append(i)
print gmpy.digits(i,2), # show in base 2
print
print
print sum(s)

## Sum of 4-bit numbers without leading 0's using popcount().
##
## 10000111 10001011 10001101 10001110
## 10010011 10010101 10010110 10011001
## 10011010 10011100 10100011 10100101
## 10100110 10101001 10101010 10101100
## 10110001 10110010 10110100 10111000
## 11000011 11000101 11000110 11001001
## 11001010 11001100 11010001 11010010
## 11010100 11011000 11100001 11100010
## 11100100 11101000 11110000
##
## 6385



for n >= m >= 1.

--- Christopher Heckman

.

Relevant Pages

  • Re: strange sum behavior
    ... the rate of summing a list seems to be over ... > its nearly 3 times faster to sum the sums of smaller lists? ... When you sum from 0 to 65,535, your sum is just over ... and becomes a Python Long. ...
    (comp.lang.python)
  • Re: Microbenchmark: Summing over array of doubles
    ... > to add up a large array of floating point numbers was one of the first ... The fastest way to sum 10 ... > calculations involve summing similarly sized values. ...
    (comp.lang.python)
  • Re: Summing Calculated Fields
    ... I added the Nz to all of my equations for the summing fields but still the ... Sum of ... It then used that duration to to calculate the ... After calculating hour in each month I am simply multiplying ...
    (microsoft.public.access.forms)
  • Re: Continuous Forms - Sum of Values
    ... You shouldn't be summing the column name, ... Given an example like an inventory balance with these 3 example ... The Disbursed sum would be... ... I have tried seting the control source to =SUM ...
    (microsoft.public.access.forms)
  • Re: sum
    ... No SUM? ... Summing 30 cells at a whack for 100 to 150 cells is a lot of typing. ... "Peo Sjoblom" wrote: ... just wrap each set of 30 in extra parenthesis ...
    (microsoft.public.excel.misc)
Quantcast