Colin Mallows's problems

[Edwin Clark]

On Sat, 11 Jun 2005, Max wrote:

> 
> Could you please compute also the number of polynomials with coefficients in {-1,0,1} that divide x^n-1 ?
> 

If I haven't made a mistake:
Here are the number of monic divisors of x^n - 1 with coefficients in 
{0,1,-1}. Multiply by 2 to get all that have coefficients in {0,1,-1}.

2, 4, 4, 8, 4, 14, 4, 16, 8, 14, 4, 48, 4, 14, 14, 32, 4, 50, 4, 48, 14, 
14, 4, 162, 8, 14, 16, 48, 4, 136, 4, 64, 14, 14, 14, 286, 4, 14, 14, 160, 
4, 136, 4, 48, 48, 14, 4, 550, 8, 50, 14, 48, 4, 186, 14, 164, 14, 14, 4, 
1124, 4, 14, 48, 128, 14, 136, 4, 48, 14, 136, 4, 1546, 4, 14, 49, 48, 14, 
136, 4, 532, 32, 14, 4, 1138, 14, 14, 14, 160, 4, 1192, 14, 48, 14, 14, 
14, 1882, 4, 50, 48, 296

Note that many of these are equal to 2^tau(n) where tau(n) is the number 
of positive divisors of n = number of irreducible factors of x^n - 1 for 
many values of n. This is connected to the fact that for small values of n 
the coefficients of the nth cyclotomic polynomial has coefficients in 
{0,1,-1}. But it is unlikely that any simple formula gives the sequence 
for all n (IMHO)... 

Please submit the sequence Max if you wish. It might be a good idea to 
have someone else check my computation.

--Edwin