cp's OEIS Frontend

A107748 Number of monic divisors of x^n - 1 with coefficients in {0,1,-1}.

%I A107748 #12 Aug 25 2017 03:00:58
%S A107748 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,
%T A107748 48,4,136,4,64,14,14,14,286,4,14,14,160,4,136,4,48,48,14,4,550,8,50,
%U A107748 14,48,4,186,14,164,14,14,4,1124,4,14,48,128,14,136,4,48,14,136
%N A107748 Number of monic divisors of x^n - 1 with coefficients in {0,1,-1}.
%C A107748 Multiply by 2 to get all that have coefficients in {0,1,-1}.
%C A107748 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. This is connected with the fact that for small values of n the coefficients of the n-th cyclotomic polynomial belong to {0,1,-1}.
%C A107748 From _Robert Israel_, Aug 24 2017: (Start)
%C A107748 Each of these polynomials is a product of distinct cyclotomic polynomials C_k(x) for k dividing n.
%C A107748 a(n) <= 2^tau(n).
%C A107748 If n is prime then a(n)=4. (End)
%H A107748 Robert Israel, <a href="/A107748/b107748.txt">Table of n, a(n) for n = 1..719</a> (n=1..359 from Antti Karttunen)
%p A107748 f:= proc(n) local t, C, x, S;
%p A107748   C:= map(m -> numtheory:-cyclotomic(m, x), numtheory:-divisors(n) );
%p A107748   t:= 0:
%p A107748   S:= combinat:-subsets(C);
%p A107748   while not S[finished] do
%p A107748   if map(abs,{coeffs(expand(convert(S[nextvalue](), `*`)), x)}) = {1} then
%p A107748     t:= t+1;
%p A107748   fi
%p A107748 od;
%p A107748 t
%p A107748 end proc:
%p A107748 map(f, [$1..100]); # _Robert Israel_, Aug 24 2017
%o A107748 (PARI) for(n=1, 359, m=0; p=x^n-1; nE=numdiv(n); P=factor(p); E=P[, 2]; P=P[, 1]; forvec(v=vector(nE, i, [0, E[i]]), divp=prod(k=1, nE, P[k]^v[k]); m++; for(j=0, poldegree(divp), divpcof=polcoeff(divp, j); if(divpcof<-1 || divpcof>1, m--; break))); write("b107748.txt", n, " ", m)); \\ _Antti Karttunen_, Aug 24 2017, after Herman Jamke's PARI-program for A107067
%Y A107748 Cf. A107067, A067824.
%K A107748 nonn
%O A107748 1,1
%A A107748 _W. Edwin Clark_, Jun 11 2005