login
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.
8

%I #13 Jul 02 2018 06:59:17

%S 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,

%T 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,

%U 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

%N 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.

%H Antti Karttunen, <a href="/A114536/b114536.txt">Table of n, a(n) for n = 1..719</a>

%H Felipe Garcia H., <a href="http://fgarciah.bol.ucla.edu/Research/research.html">Research</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 Journal of Mathematics 51 (2007) 597-604.

%H Nathan C. Ryan, <a href="http://www.math.ucla.edu/~nathan/research.html">Research</a>.

%F 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.

%e 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.

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

%o (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

%o (PARI)

%o \\ This version needs less memory:

%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 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

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

%K nonn,nice

%O 1,6

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

%E Edited and extended by _Robert G. Wilson v_, Mar 01 2006