I thought of this but I dint think of substituting x=1 .. Will surely try in a while n will reply ! Oh god how I missed x=1!

## ···

-----Original Message-----

From: "Greg Navis" <contact@gregnavis.com>

Sent: 8/31/2015 4:21 PM

To: "Ruby users" <ruby-talk@ruby-lang.org>

Subject: Re: Odd binomial coefficients

Another observation is that when you reduce P(x) mod 2 and denote the result by P_2(x) then P_2(1) evaluated in integers is the number you're looking for. This means the computations on the coefficients can be carried out in Z/2Z. This should save some memory.

On Mon, Aug 31, 2015 at 12:45 PM, Greg Navis <contact@gregnavis.com> wrote:

Applying a binomial to (1+x)^n should be easy - the coefficients are just the n-th row in the Pascal's triangle. Note that C(n, k) <= 2^n. For n = 60 we get C(n, k) <= 2^60 which means it's an at most 60-bit number.

I think you should give this approach a shot. What do you think? We can look for other ways if the exponents are really huge.

On Mon, Aug 31, 2015 at 12:11 PM, dinesh agarwal <da.230896@gmail.com> wrote:

I guess that applying binomial on (1+x)^60 will take lot of memory. Secondly applying binomial is not an easy task, that's what I think .

From: Greg Navis

Sent: 8/31/2015 3:17 PM

To: Ruby users

Subject: Re: Odd binomial coefficients

1. You can represent a polynomial using an array. For instance 1 + 2 x + 3 x^2 can be represented as [3, 2, 1]. Encapsulate the whole thing into a Polynomial class.

2. Implement the power operator as Polynomial#**. Use the binomial theorem to find the resulting coefficients.

3. Implement the addition operator as Polynomial#+.

4. Implement W(P(x)) by looking at the coefficients of an instance of Polynomial.

On Sun, Aug 30, 2015 at 10:46 AM, dinesh agarwal <da.230896@gmail.com> wrote:

was coding in ruby a question which is as follow:

If P(x) is a polynomial in x with integer coefficients, let W(P(x)) = number of odd coefficients of P(x).

Given a1, a2, ... , am, find W( (1+x)a1 + (1+x)a2 + ... + (1+x)am ).

In the ques m would be given and so a1 a2 ....am . We have to find the number of odd coefficients. Any help would be grateful.

REGARDS

Dinesh