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

%I #30 Oct 24 2023 05:00:17

%S 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 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 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 Number of polynomials with coefficients in {0,1} and which divide x^n - 1.

%C From _Robert Israel_, May 22 2017: (Start)

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

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

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

%H Robert Israel, <a href="/A107067/b107067.txt">Table of n, a(n) for n = 1..719</a> (first 359 terms from Antti Karttunen)

%p f:= proc(n) local t, C, x, S;

%p C:= map(m -> numtheory:-cyclotomic(m,x), numtheory:-divisors(n) minus {1});

%p t:= 0:

%p S:= combinat:-subsets(C);

%p while not S[finished] do

%p if {coeffs(expand(convert(S[nextvalue](),`*`)),x)} = {1} then

%p t:= t+1;

%p fi

%p od;

%p t

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, May 22 2017

%t a[n_] := Module[{c, s},

%t c = Cyclotomic[#, x]& /@ Rest@Divisors[n];

%t s = CoefficientList[#, x]& /@ (Times @@@ Subsets[c]);

%t Select[s, AllTrue[#, # == 0 || # == 1&]&] // Length];

%t Table[a[n], {n, 1, 105}] (* _Jean-François Alcover_, Oct 24 2023 *)

%o (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 Cf. A107336, A107748.

%K nonn

%O 1,2

%A _Ralf Stephan_, following a suggestion from _Max Alekseyev_, Jun 11 2005

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

%E Data section further extended and b-file computed with Jamke's PARI-program by _Antti Karttunen_, May 22 2017