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,1

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.

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.

Example

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.

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}]

Prog

(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

Crossrefs

Cf. A114536.

Sequence in context: A184233 A356386 A055077 * A011173 A162943 A131136

Adjacent sequences: A117212 A117213 A117214 * A117216 A117217 A117218

Keyword

nonn

Author

T. D. Noe, Mar 03 2006

Status

approved