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 a_1 , a_2, ... , a_m , find W( (1+x)^a_1 + (1+x)^a_2 + ... + (1+x)^a_m ).
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
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
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 .
-----Original Message-----
From: "Greg Navis" <contact@gregnavis.com>
Sent: 8/31/2015 3:17 PM
To: "Ruby users" <ruby-talk@ruby-lang.org>
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
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 <contact@gregnavis.com>
Sent: 8/31/2015 3:17 PM
To: Ruby users <ruby-talk@ruby-lang.org>
Subject: Re: Odd binomial coefficients1. 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
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 <contact@gregnavis.com>
Sent: 8/31/2015 3:17 PM
To: Ruby users <ruby-talk@ruby-lang.org>
Subject: Re: Odd binomial coefficients1. 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
Will try in a while... Btw exponents can b huge .. I would suggest searching for other approach 
-----Original Message-----
From: "Greg Navis" <contact@gregnavis.com>
Sent: 8/31/2015 4:15 PM
To: "Ruby users" <ruby-talk@ruby-lang.org>
Subject: Re: Odd binomial coefficients
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
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