Colin Mallows's problems

[Max]

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.
> 
> 
> What's about a sequence of such n's? Is it finite or infinite?

This sequence seems to consist of primes and powers of primes. Is there a proof that no other number can be an element of this sequence.

>>  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.
> 
> 
> What method did you use to compute these numbers?
> Did you make all possible divisors of x^n - 1 out of cyclotomic 
> polynomials of degree dividing n and then test their coefficients?

I've done my own computations and but they confirm yours.

{test1(p) = local(c); for(i=0,poldegree(p),if(abs(polcoeff(p,i))>1,return(0)));1}
{a(n) = local(d,r,t); d=divisors(n); r=0; for(s=0,2^length(d)-1,t=vecextract(d,s);r+=test1(prod(i=1,length(t),polcyclo(t[i]))));r}
for(n=1,100,print1(" ",a(n)))

  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

Max