Author |
Topic: factorize (Read 2853 times) |
|
balakrishnan
Junior Member
Gender: 
Posts: 92
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: factorize
« Reply #1 on: Aug 9th, 2007, 10:16am » |
 Quote  Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: factorize
« Reply #2 on: Aug 9th, 2007, 12:47pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: factorize
« Reply #3 on: Aug 9th, 2007, 1:18pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: factorize
« Reply #4 on: Aug 10th, 2007, 12:42am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: factorize
« Reply #5 on: Aug 10th, 2007, 8:17am » |
Quote Modify
|
ya.I guess you must be also looking for
(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)) 
|
| « Last Edit: Aug 10th, 2007, 1:41pm by balakrishnan » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: factorize
« Reply #6 on: Aug 11th, 2007, 4:04pm » |
Quote Modify
|
Or maybe
| hidden: |
(x74 + x68 + x62 + x20 + x14 + x8)
* (x73 + x72 + x71 + x-35 + x-36 + x-37)
* (x69 + x66 + x51 + x48 + x33 + x30)
|
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: factorize
« Reply #7 on: Aug 12th, 2007, 7:16am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
balakrishnan
Junior Member
Gender:
Posts: 92
|
|
Re: factorize
« Reply #9 on: Aug 14th, 2007, 7:01am » |
Quote Modify
|
or may be
(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)
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: factorize
« Reply #10 on: Jul 25th, 2008, 10:52pm » |
Quote Modify
|
For n 6-sided dice, the number of ways is the denominator of the n-th convergent of (e-1)/2!  Truly amazing. 
Okay I haven't actually shown that yet, but it is
N(n) =  k=0n D(n,k)*C(n,k)2,
where
D(n,k) = i=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,...) = 1, 7, 71, 1001,.... [Edit: Actually I think it will be clear that N(n)*n! = A033815]
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  d. Now, (x6^n-1-1)/(x-1) is the product of all (n+1)2-1 squares d 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 d, over d=(i, k), k  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 d, over d=(k, j), k 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 j1 j2 ... jn 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 j2 ... jn 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.]
|
| « Last Edit: Jul 25th, 2008, 11:29pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print