Colin Mallows's problems

[Edwin Clark]

On Sun, 12 Jun 2005, Max wrote:

> Edwin Clark wrote:

> > 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?

It will be true at least for all primes. In this case x^n-1 = 
(x-1)(x^(n-1) + . . . + x + 1) and when n is prime both factors are 
irreducible. So these two factors (corresponding to tau(n) = 2), 1, and 
x^n-1 are 2^2 monic factors with coefficients in {0,1,-1}. Computations 
show that at least for n <= 100 that only primes and prime powers have 
a(n) = 2^tau(n) = total number of divisors of x^n-1 with coefficients 
0,1,-1.

> 
> 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 used maple to find the tau(n) factors of x^n-1 and then multiplied them 
together in all possible ways and counted those with coefficients 0,1,-1.
Since maple has a builtin cyclotomic polynomial generator, I could have 
generated the factors using it.But I chose not to.  Here's the maple 
program: (No doubt it can be improved.)

  isgood:=proc(f)
    evalb({coeffs(f)} subset {1,-1});
  end proc:

  a:=proc(n)
  local L1,x,L,S,count,t;
  if n = 1 then return 2; fi;
  L1:=factor(x^n-1);
  L:=[op(L1)];
  S:=combinat:-powerset(nops(L)) minus {{}};
  count:=1:
  for t in S do
    if isgood(expand(product(L[t[i]],i=1..nops(t)))) then 
      count:=count+1; 
    end if;
  end do: 
  count;
  end proc: