A107067 Number of polynomials with coefficients in {0,1} and which divide x^n - 1.

1, 2, 2, 4, 2, 6, 2, 8, 4, 6, 2, 17, 2, 6, 6, 16, 2, 18, 2, 17, 6, 6, 2, 48, 4, 6, 8, 17, 2, 36, 2, 32, 6, 6, 6, 69, 2, 6, 6, 47, 2, 36, 2, 17, 17, 6, 2, 136, 4, 18, 6, 17, 2, 54, 6, 47, 6, 6, 2, 176, 2, 6, 17, 64, 6, 36, 2, 17, 6, 36, 2, 257, 2, 6, 18, 17, 6, 36, 2, 131, 16, 6, 2, 177, 6, 6, 6, 47, 2, 183, 6, 17, 6, 6, 6, 389, 2, 18, 17, 70, 2, 36, 2, 47, 35

Offset: 1

Author

Ralf Stephan, following a suggestion from Max Alekseyev, Jun 11 2005

Keywords

• nonn

Comments

From Robert Israel, May 22 2017: (Start)

Each of these polynomials is a product of distinct cyclotomic polynomials C_k(x) for k > 1 dividing n.

a(n) <= 2^(A000005(n)-1).

If n is prime then a(n) = 2. (End)

Links

• Robert Israel, Table of n, a(n) for n = 1..719 (first 359 terms from Antti Karttunen)

Crossrefs

Cf. A107336, A107748.

Programs

Maple

f:= proc(n) local t, C, x, S;
  C:= map(m -> numtheory:-cyclotomic(m,x), numtheory:-divisors(n) minus {1});
  t:= 0:
  S:= combinat:-subsets(C);
  while not S[finished] do
  if {coeffs(expand(convert(S[nextvalue](),`*`)),x)} = {1} then
    t:= t+1;
  fi
od;
t
end proc:
map(f, [$1..100]); # Robert Israel, May 22 2017

Mathematica

a[n_] := Module[{c, s},
  c = Cyclotomic[#, x]& /@ Rest@Divisors[n];
  s = CoefficientList[#, x]& /@ (Times @@@ Subsets[c]);
  Select[s, AllTrue[#, # == 0 || # == 1&]&] // Length];
Table[a[n], {n, 1, 105}] (* Jean-François Alcover, Oct 24 2023 *)

PARI

for(n=1,100,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<0 || divpcof>1,m--;break)));print1(m,",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 15 2006

Extensions

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 15 2006

Data section further extended and b-file computed with Jamke's PARI-program by Antti Karttunen, May 22 2017