wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> factorize
        
(Message started by: balakrishnan on Aug 9th, 2007, 9:16am)
Title: factorize
Post by balakrishnan on Aug 9th, 2007, 9:16am
find all possible ways to factorize the polynomial
(x^216-1)/(x-1)
into 3 factors p(x) q(x) r(x)
such that
(x^216-1)/(x-1)=p(x)*q(x)*r(x)
such that each of p(x),q(x) and r(x) have 6 terms
and the coefficient of each term in p(x),q(x) and r(x) is +1
One trivial way is
p(x)=1+x+x^2+x^3+x^4+x^5
q(x)=1+x^6+x^12+x^18+x^24+x^30
r(x)=1+x^36+x^72+x^108+x^144+x^180
Title: Re: factorize
Post by towr on Aug 9th, 2007, 10:16am
You need three sets of 6 distinct (non negative) numbers so that if you can get any number from 0-215 by summing picking a number from each set and summing these three numbers.
Easy enough to have a computer search it, but you probably want something more clever.

One obvious observation is that 0 must be in all three sets, or you can't get 0 by summing. So that leaves the other 5 numbers per set.
Title: Re: factorize
Post by balakrishnan on Aug 9th, 2007, 12:47pm
There are all the factorizations I have obtained:
(x^45+x^36+x^27+x^18+x^9+1)(x^60+x^57+x^54+x^6+x^3+1)(x^110+x^109+x^108+x^2+x^1+1)
(x^45+x^36+x^27+x^18+x^9+1)(x^114+x^111+x^108+x^6+x^3+1)(x^56+x^55+x^54+x^2+x^1+1)
(x^72+x^63+x^54+x^18+x^9+1)(x^33+x^30+x^27+x^6+x^3+1)(x^110+x^109+x^108+x^2+x^1+1)
(x^72+x^63+x^54+x^18+x^9+1)(x^114+x^111+x^108+x^6+x^3+1)(x^29+x^28+x^27+x^2+x^1+1)
(x^126+x^117+x^108+x^18+x^9+1)(x^33+x^30+x^27+x^6+x^3+1)(x^56+x^55+x^54+x^2+x^1+1)
(x^126+x^117+x^108+x^18+x^9+1)(x^60+x^57+x^54+x^6+x^3+1)(x^29+x^28+x^27+x^2+x^1+1)
(x^90+x^72+x^54+x^36+x^18+1)(x^15+x^12+x^9+x^6+x^3+1)(x^110+x^109+x^108+x^2+x^1+1)
(x^90+x^72+x^54+x^36+x^18+1)(x^114+x^111+x^108+x^6+x^3+1)(x^11+x^10+x^9+x^2+x^1+1)
(x^144+x^126+x^108+x^36+x^18+1)(x^15+x^12+x^9+x^6+x^3+1)(x^56+x^55+x^54+x^2+x^1+1)
(x^144+x^126+x^108+x^36+x^18+1)(x^60+x^57+x^54+x^6+x^3+1)(x^11+x^10+x^9+x^2+x^1+1)
(x^39+x^21+x^3+x^36+x^18+1)(x^66+x^60+x^54+x^12+x^6+1)(x^110+x^109+x^108+x^2+x^1+1)
(x^39+x^21+x^3+x^36+x^18+1)(x^120+x^114+x^108+x^12+x^6+1)(x^56+x^55+x^54+x^2+x^1+1)
(x^90+x^72+x^54+x^36+x^18+1)(x^120+x^114+x^108+x^12+x^6+1)(x^5+x^4+x^3+x^2+x^1+1)
(x^144+x^126+x^108+x^36+x^18+1)(x^66+x^60+x^54+x^12+x^6+1)(x^5+x^4+x^3+x^2+x^1+1)
(x^37+x^19+x^1+x^36+x^18+1)(x^66+x^60+x^54+x^12+x^6+1)(x^112+x^110+x^108+x^4+x^2+1)
(x^37+x^19+x^1+x^36+x^18+1)(x^120+x^114+x^108+x^12+x^6+1)(x^58+x^56+x^54+x^4+x^2+1)
(x^90+x^72+x^54+x^36+x^18+1)(x^13+x^7+x^1+x^12+x^6+1)(x^112+x^110+x^108+x^4+x^2+1)
(x^144+x^126+x^108+x^36+x^18+1)(x^13+x^7+x^1+x^12+x^6+1)(x^58+x^56+x^54+x^4+x^2+1)
(x^81+x^45+x^9+x^72+x^36+1)(x^24+x^21+x^18+x^6+x^3+1)(x^110+x^109+x^108+x^2+x^1+1)
(x^81+x^45+x^9+x^72+x^36+1)(x^114+x^111+x^108+x^6+x^3+1)(x^20+x^19+x^18+x^2+x^1+1)
(x^180+x^144+x^108+x^72+x^36+1)(x^15+x^12+x^9+x^6+x^3+1)(x^20+x^19+x^18+x^2+x^1+1)
(x^180+x^144+x^108+x^72+x^36+1)(x^24+x^21+x^18+x^6+x^3+1)(x^11+x^10+x^9+x^2+x^1+1)
(x^75+x^39+x^3+x^72+x^36+1)(x^30+x^24+x^18+x^12+x^6+1)(x^110+x^109+x^108+x^2+x^1+1)
(x^75+x^39+x^3+x^72+x^36+1)(x^120+x^114+x^108+x^12+x^6+1)(x^20+x^19+x^18+x^2+x^1+1)
(x^180+x^144+x^108+x^72+x^36+1)(x^30+x^24+x^18+x^12+x^6+1)(x^5+x^4+x^3+x^2+x^1+1)
(x^73+x^37+x^1+x^72+x^36+1)(x^30+x^24+x^18+x^12+x^6+1)(x^112+x^110+x^108+x^4+x^2+1)
(x^73+x^37+x^1+x^72+x^36+1)(x^120+x^114+x^108+x^12+x^6+1)(x^22+x^20+x^18+x^4+x^2+1)
(x^180+x^144+x^108+x^72+x^36+1)(x^13+x^7+x^1+x^12+x^6+1)(x^22+x^20+x^18+x^4+x^2+1)
(x^75+x^39+x^3+x^72+x^36+1)(x^132+x^120+x^108+x^24+x^12+1)(x^8+x^7+x^6+x^2+x^1+1)
(x^78+x^42+x^6+x^72+x^36+1)(x^27+x^15+x^3+x^24+x^12+1)(x^110+x^109+x^108+x^2+x^1+1)
(x^78+x^42+x^6+x^72+x^36+1)(x^132+x^120+x^108+x^24+x^12+1)(x^5+x^4+x^3+x^2+x^1+1)
(x^180+x^144+x^108+x^72+x^36+1)(x^27+x^15+x^3+x^24+x^12+1)(x^8+x^7+x^6+x^2+x^1+1)
(x^73+x^37+x^1+x^72+x^36+1)(x^132+x^120+x^108+x^24+x^12+1)(x^10+x^8+x^6+x^4+x^2+1)
(x^78+x^42+x^6+x^72+x^36+1)(x^25+x^13+x^1+x^24+x^12+1)(x^112+x^110+x^108+x^4+x^2+1)
(x^180+x^144+x^108+x^72+x^36+1)(x^25+x^13+x^1+x^24+x^12+1)(x^10+x^8+x^6+x^4+x^2+1)
(x^73+x^37+x^1+x^72+x^36+1)(x^26+x^14+x^2+x^24+x^12+1)(x^116+x^112+x^108+x^8+x^4+1)
(x^74+x^38+x^2+x^72+x^36+1)(x^25+x^13+x^1+x^24+x^12+1)(x^116+x^112+x^108+x^8+x^4+1)
(x^74+x^38+x^2+x^72+x^36+1)(x^132+x^120+x^108+x^24+x^12+1)(x^9+x^5+x^1+x^8+x^4+1)
(x^180+x^144+x^108+x^72+x^36+1)(x^26+x^14+x^2+x^24+x^12+1)(x^9+x^5+x^1+x^8+x^4+1)
(x^153+x^81+x^9+x^144+x^72+1)(x^24+x^21+x^18+x^6+x^3+1)(x^38+x^37+x^36+x^2+x^1+1)
(x^153+x^81+x^9+x^144+x^72+1)(x^42+x^39+x^36+x^6+x^3+1)(x^20+x^19+x^18+x^2+x^1+1)
(x^162+x^90+x^18+x^144+x^72+1)(x^15+x^12+x^9+x^6+x^3+1)(x^38+x^37+x^36+x^2+x^1+1)
(x^162+x^90+x^18+x^144+x^72+1)(x^42+x^39+x^36+x^6+x^3+1)(x^11+x^10+x^9+x^2+x^1+1)
(x^147+x^75+x^3+x^144+x^72+1)(x^30+x^24+x^18+x^12+x^6+1)(x^38+x^37+x^36+x^2+x^1+1)
(x^147+x^75+x^3+x^144+x^72+1)(x^48+x^42+x^36+x^12+x^6+1)(x^20+x^19+x^18+x^2+x^1+1)
(x^162+x^90+x^18+x^144+x^72+1)(x^48+x^42+x^36+x^12+x^6+1)(x^5+x^4+x^3+x^2+x^1+1)
(x^145+x^73+x^1+x^144+x^72+1)(x^30+x^24+x^18+x^12+x^6+1)(x^40+x^38+x^36+x^4+x^2+1)
(x^145+x^73+x^1+x^144+x^72+1)(x^48+x^42+x^36+x^12+x^6+1)(x^22+x^20+x^18+x^4+x^2+1)
(x^162+x^90+x^18+x^144+x^72+1)(x^13+x^7+x^1+x^12+x^6+1)(x^40+x^38+x^36+x^4+x^2+1)
(x^147+x^75+x^3+x^144+x^72+1)(x^60+x^48+x^36+x^24+x^12+1)(x^8+x^7+x^6+x^2+x^1+1)
(x^150+x^78+x^6+x^144+x^72+1)(x^27+x^15+x^3+x^24+x^12+1)(x^38+x^37+x^36+x^2+x^1+1)
(x^150+x^78+x^6+x^144+x^72+1)(x^60+x^48+x^36+x^24+x^12+1)(x^5+x^4+x^3+x^2+x^1+1)
(x^145+x^73+x^1+x^144+x^72+1)(x^60+x^48+x^36+x^24+x^12+1)(x^10+x^8+x^6+x^4+x^2+1)
(x^150+x^78+x^6+x^144+x^72+1)(x^25+x^13+x^1+x^24+x^12+1)(x^40+x^38+x^36+x^4+x^2+1)
(x^145+x^73+x^1+x^144+x^72+1)(x^26+x^14+x^2+x^24+x^12+1)(x^44+x^40+x^36+x^8+x^4+1)
(x^146+x^74+x^2+x^144+x^72+1)(x^25+x^13+x^1+x^24+x^12+1)(x^44+x^40+x^36+x^8+x^4+1)
(x^146+x^74+x^2+x^144+x^72+1)(x^60+x^48+x^36+x^24+x^12+1)(x^9+x^5+x^1+x^8+x^4+1)
(x^147+x^75+x^3+x^144+x^72+1)(x^54+x^30+x^6+x^48+x^24+1)(x^14+x^13+x^12+x^2+x^1+1)
(x^150+x^78+x^6+x^144+x^72+1)(x^51+x^27+x^3+x^48+x^24+1)(x^14+x^13+x^12+x^2+x^1+1)
(x^156+x^84+x^12+x^144+x^72+1)(x^51+x^27+x^3+x^48+x^24+1)(x^8+x^7+x^6+x^2+x^1+1)
(x^156+x^84+x^12+x^144+x^72+1)(x^54+x^30+x^6+x^48+x^24+1)(x^5+x^4+x^3+x^2+x^1+1)
(x^145+x^73+x^1+x^144+x^72+1)(x^54+x^30+x^6+x^48+x^24+1)(x^16+x^14+x^12+x^4+x^2+1)
(x^150+x^78+x^6+x^144+x^72+1)(x^49+x^25+x^1+x^48+x^24+1)(x^16+x^14+x^12+x^4+x^2+1)
(x^156+x^84+x^12+x^144+x^72+1)(x^49+x^25+x^1+x^48+x^24+1)(x^10+x^8+x^6+x^4+x^2+1)
(x^145+x^73+x^1+x^144+x^72+1)(x^50+x^26+x^2+x^48+x^24+1)(x^20+x^16+x^12+x^8+x^4+1)
(x^146+x^74+x^2+x^144+x^72+1)(x^49+x^25+x^1+x^48+x^24+1)(x^20+x^16+x^12+x^8+x^4+1)
(x^156+x^84+x^12+x^144+x^72+1)(x^50+x^26+x^2+x^48+x^24+1)(x^9+x^5+x^1+x^8+x^4+1)
(x^145+x^73+x^1+x^144+x^72+1)(x^52+x^28+x^4+x^48+x^24+1)(x^18+x^10+x^2+x^16+x^8+1)
(x^146+x^74+x^2+x^144+x^72+1)(x^52+x^28+x^4+x^48+x^24+1)(x^17+x^9+x^1+x^16+x^8+1)
(x^148+x^76+x^4+x^144+x^72+1)(x^49+x^25+x^1+x^48+x^24+1)(x^18+x^10+x^2+x^16+x^8+1)
(x^148+x^76+x^4+x^144+x^72+1)(x^50+x^26+x^2+x^48+x^24+1)(x^17+x^9+x^1+x^16+x^8+1)

This is a combination of analysis and programming.
I figured out that each of the 3 terms has to be of the form
(1+x^a)(1+x^n+x^(2n))


I was wondering if there is a neat analytical approach using cyclotomic polynomials.
Title: Re: factorize
Post by balakrishnan on Aug 9th, 2007, 1:18pm
If
p(x)=(1+x^a)(1+x^n+x^(2n))
q(x)=(1+x^b)(1+x^m+x^(2m))
r(x)=(1+x^c)(1+x^p+x^(2p))

then we see that
the original polynomial has roots
exp(2*pi*k/216) for k=1 to 215

we need n,m,p such that
k1/n !=k2/m for 1<=k1<=n and 1<=k2<=m
k1/n !=k3/p for 1<=k1<=n and 1<=k3<=p
k2/m !=k3/p for 1<=k2<=m and 1<=k3<=p

because if there they exists then clearly the roots of n,m,p overlap.
Once you find such a triplet,search for a,b,c to fill in the gaps.
Title: Re: factorize
Post by Grimbal on Aug 10th, 2007, 12:42am
I think it is not a coincidence that the problem is related to the question:
How to design 3 dice, each having 6 faces, such that throwing the dice and summing the faces shown can give all the values from 0 to 215.
Title: Re: factorize
Post by balakrishnan on Aug 10th, 2007, 8:17am
ya.I guess you must be also looking for
[hide](x^74+x^70+x^71+x^72+x^73+x^69)(x^67+x^43+x^49+x^55+x^61+x^37)(x^75+x^(-69)+x^(-33)+x^3+x^39+x^(-105))[/hide] ::)
Title: Re: factorize
Post by Grimbal on Aug 11th, 2007, 4:04pm
Or maybe
[hideb]
(x74 + x68 + x62 + x20 + x14 + x8)
* (x73 + x72 + x71 + x-35 + x-36 + x-37)
* (x69 + x66 + x51 + x48 + x33 + x30)
[/hideb]
:-/
Title: Re: factorize
Post by towr on Aug 12th, 2007, 7:16am
There are obviously infinitely many solutions if you allow negative exponents.
Just multiply any of p(x),q(x),r(x) by x, and divide another by x.


I don't think you'd get any really new ones.
Title: Re: factorize
Post by Grimbal on Aug 12th, 2007, 12:50pm
It was in reference to the following problem

http://www.puzzleup.com/puzzle/?201
Title: Re: factorize
Post by balakrishnan on Aug 14th, 2007, 7:01am
or may be
[hide]
(x^-37+x^-36+x^-35+x^71+x^72+x^73)(x^9+x^12+x^15+x^63+x^66+x^69)(x^29+x^38+x^47+x^56+x^65+x^74)
(x^-37+x^-36+x^-35+x^71+x^72+x^73)(x^8+x^14+x^20+x^62+x^68+x^74)(x^30+x^48+x^66+x^33+x^51+x^69)
(x^-40+x^-39+x^-38+x^68+x^69+x^70)(x^6+x^12+x^18+x^60+x^66+x^72)(x^35+x^53+x^71+x^38+x^56+x^74)
(x^-38+x^-36+x^-34+x^70+x^72+x^74)(x^7+x^13+x^19+x^61+x^67+x^73)(x^32+x^50+x^68+x^33+x^51+x^69)
(x^-43+x^-41+x^-39+x^65+x^67+x^69)(x^8+x^14+x^20+x^62+x^68+x^74)(x^36+x^54+x^72+x^37+x^55+x^73)[/hide]
:'(
Title: Re: factorize
Post by Eigenray on Jul 25th, 2008, 10:52pm
For n 6-sided dice, the number of ways is [hide]the denominator of the n-th convergent of (e-1)/2[/hide]!   :o  Truly amazing.  :D

Okay I haven't actually shown that yet, but it is

N(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifk=0n  D(n,k)*C(n,k)2,

where

D(n,k) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi=0k  (-1)iC(k,i)(n-i)!

is the number of permutations of {1,...,n} that do not fix any of {1,...,k}.

Thus N(1,2,3,4,...) = [link=http://www.research.att.com/~njas/sequences/A002119]1, 7, 71, 1001,...[/link].  [Edit: Actually I think it will be clear that N(n)*n! = [link=http://www.research.att.com/~njas/sequences/A033815]A033815[/link]

Poof: Consider an (n+1)x(n+1) matrix, rows labelled by i=0..n, columns by j=0..n.  Square (i, j) represents the number d=2i3j, as well as the cyclotomic polynomial http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifd.  Now, (x6^n-1-1)/(x-1) is the product of all (n+1)2-1 squares http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifd other than d=1=(0,0), and we want to partition this into n factors, each of which has the form (1+xa)(1+xb+x2b).  

If a=(i-1, j)=2i-13j, then 1+xa is the product of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifd, over d=(i, k), k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif j.  That is, if we pick a square a, then 1+xa represents all squares directly to the left of (and including) 2a=(i, j).  Similarly, if b=(i, j-1), then 1+xb+x2b is the product of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gifd, over d=(k, j), k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif i.  So if we pick a square b, 1+xb+x2b represents all squares directly above (and including) 3b=(i, j).

Thus we need to partition the (n+1)x(n+1) grid (except for the upper-left corner) into n horizontal strips and n vertical strips, such that each strip touches an upper/left wall.  So it is clear that we need to pick exactly one number 2a from each row 1..n.  Call these numbers (i, ji), i=1..n.  Note that
0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif j1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif j2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif ... http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif jn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n,
and furthermore, any such choice of ji's gives a unique choice for the b's: the numbers 3b are given by (ij, j), j=1..n, where ij is the largest i such that ji < j (take i0=j0=0).

Here is an example with n=3.  Pick the points 2a = (1,0), (2,1), (3,2).  This forces 3b = (1,1), (2,2), (3,3).  If we pair them up in the same order they are written:
a=(0,0)=1, b=(1,0)=2, (1+x)(1+x2+x4)
a=(1,1)=6, b=(2,1)=12, (1+x6)(1+x12+x24)
a=(2,2)=36, b=(3,2)=72, (1+x36)(1+x72+x144).

But we could have paired them up in 3! different ways, e.g. (a,b)={(1,2),(6,72),(36,12)} is another way.

But!  Note that the pairs (a,b)={(3,1),(6,72),(12,24)} give exactly the same factors.  More generally, (1+x3c)(1+xc+x2c) = (1+xc)(1+x2c+x4c), so (a,b)=(3c,c) gives the same factor as (a,b)=(c,2c).  But this is all: if we want to decompose a factor into a horizontal slice 1+xa, and a vertical slice 1+xb+x2b, there is only ambiguity when the tips are adjacent, in which case there are two possibilities for who gets the corner.

Now, how do we count around this?  We simply do not count pairings where the vertical piece gets the corner.  This can happen only at a 'jump': j=ji < ji+1.  Then we forbid the horizontal piece terminating at (i, j) to be paired with the vertical piece terminating at (i, j+1).

Suppose there are k jumps.  To be precise here I mean the number of strict inequalities in
j1 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif j2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif ... http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifjn http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n.

There are n places a jump can occur, so C(n,k) ways to place k jumps.  But k jumps means that the above numbers take on k+1 different values in [0,n], but n is always taken, so there are C(n,k) ways to pick the values.  Thus there are C(n,k)2 sequences with k jumps.  (Check: these add up to C(2n,n), the total number of such sequences.)

If we have a sequence with k jumps, then there are k forbidden pairings, and note that these involve distinct a's and b's.  So the number of ways to match the a's with b's is the same as the number of permutations on [1,n] which do not fix anything in [1,k].  This is counted by D(n,k).

Well, better late than never, eh?

[Edit: I should add that the non-zero coefficients of (1+xa)(1+xb+x2b) are all 1s: if you draw it, it is clear that a=b or a=2b is impossible.  So we never get the same number appearing twice on one die, if that is one of your conditions.  Also, an algorithm to generate all possible dice is implicit in the proof.]


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board