login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A117215 Number of divisors of x^n-1 having the maximal height A114536(n). 2
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 (list; graph; refs; listen; history; text; internal format)
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

Needs["DiscreteMath`Combinatorica`"]; 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: A095061 A184233 A055077 * A011173 A162943 A131136

Adjacent sequences:  A117212 A117213 A117214 * A117216 A117217 A117218

KEYWORD

nonn

AUTHOR

T. D. Noe, Mar 03 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 06:56 EDT 2021. Contains 345157 sequences. (Running on oeis4.)