A117215 Number of divisors of x^n-1 having the maximal height A114536(n).

2, 4, 4, 8, 4, 2, 4, 16, 8, 2, 4, 2, 4, 2, 1, 32, 4, 14, 4, 2, 1, 2, 4, 20, 8, 2, 16, 2, 4, 2, 4, 64, 1, 2, 1, 18, 4, 2, 1, 2, 4, 2, 4, 2, 2, 2, 4, 2, 8, 14, 1, 2, 4, 70, 1, 2, 1, 2, 4, 2, 4, 2, 1, 128, 1, 2, 4, 2, 1, 2, 4, 10, 4, 2, 8, 2, 1, 2, 4, 4, 32, 2, 4, 2, 1, 2, 1, 2, 4, 2, 1, 2, 1, 2, 1, 32, 4, 14

Offset: 1

Author

T. D. Noe, Mar 03 2006

Keywords

• nonn

Comments

Let p be a prime. Then a(p)=4 because the divisors are x^p-1, x^(p-1)+x^(p-2)+...+1, x-1 and 1. Similarly, a(p^k)=2^(k+1). For n=p*2^k, a(n)=2. For odd primes p and q, a(pq)=1. Conjectures: if n is odd and squarefree, then a(n)=1; if n/2^k is odd and squarefree for k>0, then a(n)=2. All the divisors of x^n-1 are products of cyclotomic polynomials cyclo(d) for various d. When n is the product of distinct odd primes p1..pk, it appears that each cyclotomic index has the form d=p1^e1...pk^ek, where the ei are either 0 or 1 and sum(ei) is odd.

Examples

			a(6)=2 because x^3+2x^2+2x+1 and x^3-2x^2+2x-1 both divide x^6-1. In fact, their product is x^6-1.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..719
• Carl Pomerance and Nathan C. Ryan, The maximal height of divisors of x^n-1, Illinois J. Math. 51 (2007), no. 2, 597-604.

Crossrefs

Cf. A114536.

Programs

Mathematica

cyc[n_] := cyc[n] = Cyclotomic[n,x];
PolyHeight[p_] := Max[Abs[CoefficientList[p,x]]];
Table[sd=Subsets[Divisors[n]]; t=Table[PolyHeight[Expand[Product[ cyc[sd[[i,j]]], {j,Length[sd[[i]]]}]]], {i,Length[sd]}]; Length[ Position[t, Max[t]]], {n,105}]

PARI

prod_by_bits(bits, fs) = { my(m=1,i=1); while(bits>0, if((bits%2),m *= fs[i]); i++; bits >>= 1); (m); };
A117215(n) = { my(fs=factor('x^n - 1)[,1],m=0,d,mds=0,k); for(b=0,(2^#fs)-1,d = prod_by_bits(b,fs); k = 0; for(j=0,poldegree(d),k = max(k,abs(polcoeff(d,j)))); if(k==m, mds++, if(k>m, mds=1; m = k))); (mds); }; \\ Antti Karttunen, Jul 01 2018