A114536 Let the height of a polynomial be the largest coefficient in absolute value. Then a(n) is the maximal height of a divisor of x^n-1 with integral coefficients.
1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 3, 1, 1, 2, 1, 4, 3, 2, 1, 3, 1, 2, 1, 4, 1, 12, 1, 1, 3, 2, 5, 4, 1, 2, 3, 5, 1, 12, 1, 4, 5, 2, 1, 6, 1, 2, 3, 4, 1, 2, 5, 7, 3, 2, 1, 54, 1, 2, 7, 1, 5, 12, 1, 4, 3, 32, 1, 8, 1, 2, 3, 4, 7, 12, 1, 7, 1, 2, 1, 55, 5, 2, 3, 8, 1, 58, 7, 4, 3, 2, 5, 6, 1, 2, 9, 4, 1, 12
Offset: 1
Examples
a(6)=2 since (x+1)(x^2+x+1)=x^3+2x^2+2x+1 divides x^6-1 and no other divisor has a greater height.
Links
- Antti Karttunen, Table of n, a(n) for n = 1..719
- Felipe Garcia H., Research.
- Carl Pomerance and Nathan C. Ryan, The maximal height of divisors of x^n-1, Illinois Journal of Mathematics 51 (2007) 597-604.
- Nathan C. Ryan, Research.
Crossrefs
Cf. A117215 (number of divisors of x^n-1 having the maximal height).
Programs
-
Mathematica
cyc[n_] := cyc[n] = Cyclotomic[n, x]; f[n_] := Block[{sd = Rest@ Subsets@ Divisors@ n, lst = {}, lmt = 2^DivisorSigma[0, n]}, For[i = 1, i < lmt, i++, AppendTo[lst, Max@ Abs@ CoefficientList[ Expand[ Times @@ (cyc[ # ] & /@ sd[[i]])], x]]]; Max@lst]; Array[f, 102] (* Robert G. Wilson v, Mar 01 2006 *) -
PARI
A114536(n) = { my(ds=divisors('x^n - 1),m=0); for(i=1,length(ds),for(j=0,poldegree(ds[i]),m = max(m,abs(polcoeff(ds[i],j))))); (m); }; \\ Antti Karttunen, Jul 01 2018
-
PARI
\\ This version needs less memory: prod_by_bits(bits, fs) = { my(m=1,i=1); while(bits>0, if((bits%2),m *= fs[i]); i++; bits >>= 1); (m); }; A114536(n) = { my(fs=factor('x^n - 1)[,1],m=0,d); for(b=1,(2^#fs)-1,d = prod_by_bits(b,fs); for(j=0,poldegree(d),m = max(m,abs(polcoeff(d,j))))); (m); }; \\ Antti Karttunen, Jul 01 2018
Formula
a(n)=1 iff n=1 or n=p^k where p is a prime and k is a positive integer; a(pq)=min{p,q} where p and q are distinct primes.
Extensions
Edited and extended by Robert G. Wilson v, Mar 01 2006