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

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.

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.

Example

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.

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 *)

Prog

(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

Crossrefs

Cf. A117215 (number of divisors of x^n-1 having the maximal height).

Sequence in context: A345994 A052128 A284600 * A330692 A349658 A345992

Adjacent sequences: A114533 A114534 A114535 * A114537 A114538 A114539

Keyword

nonn,nice

Author

Felipe Garcia (fgarciah(AT)ucla.edu), Feb 15 2006

Extensions

Edited and extended by Robert G. Wilson v, Mar 01 2006

Status

approved