|
%I #19 Jul 15 2022 03:49:15
%S 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,
%T 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,
%U 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
%N Number of divisors of x^n-1 having the maximal height A114536(n).
%C 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.
%H Antti Karttunen, <a href="/A117215/b117215.txt">Table of n, a(n) for n = 1..719</a>
%H Carl Pomerance and Nathan C. Ryan, <a href="http://projecteuclid.org/euclid.ijm/1258138432">The maximal height of divisors of x^n-1</a>, Illinois J. Math. 51 (2007), no. 2, 597-604.
%e 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.
%t cyc[n_] := cyc[n] = Cyclotomic[n,x];
%t PolyHeight[p_] := Max[Abs[CoefficientList[p,x]]];
%t 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}]
%o (PARI)
%o prod_by_bits(bits, fs) = { my(m=1,i=1); while(bits>0, if((bits%2),m *= fs[i]); i++; bits >>= 1); (m); };
%o 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
%Y Cf. A114536.
%K nonn
%O 1,1
%A _T. D. Noe_, Mar 03 2006
|
