cp's OEIS Frontend

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

%I A107067 #30 Oct 24 2023 05:00:17
%S A107067 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,
%T A107067 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,
%U A107067 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
%N A107067 Number of polynomials with coefficients in {0,1} and which divide x^n - 1.
%C A107067 From _Robert Israel_, May 22 2017: (Start)
%C A107067 Each of these polynomials is a product of distinct cyclotomic polynomials C_k(x) for k > 1 dividing n.
%C A107067 a(n) <= 2^(A000005(n)-1).
%C A107067 If n is prime then a(n) = 2. (End)
%H A107067 Robert Israel, <a href="/A107067/b107067.txt">Table of n, a(n) for n = 1..719</a> (first 359 terms from Antti Karttunen)
%p A107067 f:= proc(n) local t, C, x, S;
%p A107067   C:= map(m -> numtheory:-cyclotomic(m,x), numtheory:-divisors(n) minus {1});
%p A107067   t:= 0:
%p A107067   S:= combinat:-subsets(C);
%p A107067   while not S[finished] do
%p A107067   if {coeffs(expand(convert(S[nextvalue](),`*`)),x)} = {1} then
%p A107067     t:= t+1;
%p A107067   fi
%p A107067 od;
%p A107067 t
%p A107067 end proc:
%p A107067 map(f, [$1..100]); # _Robert Israel_, May 22 2017
%t A107067 a[n_] := Module[{c, s},
%t A107067   c = Cyclotomic[#, x]& /@ Rest@Divisors[n];
%t A107067   s = CoefficientList[#, x]& /@ (Times @@@ Subsets[c]);
%t A107067   Select[s, AllTrue[#, # == 0 || # == 1&]&] // Length];
%t A107067 Table[a[n], {n, 1, 105}] (* _Jean-François Alcover_, Oct 24 2023 *)
%o A107067 (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
%Y A107067 Cf. A107336, A107748.
%K A107067 nonn
%O A107067 1,2
%A A107067 _Ralf Stephan_, following a suggestion from _Max Alekseyev_, Jun 11 2005
%E A107067 More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 15 2006
%E A107067 Data section further extended and b-file computed with Jamke's PARI-program by _Antti Karttunen_, May 22 2017