A051664 a(n) is the number of nonzero coefficients in the n-th cyclotomic polynomial.

2, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 7, 2, 17, 3, 19, 5, 9, 11, 23, 3, 5, 13, 3, 7, 29, 7, 31, 2, 15, 17, 17, 3, 37, 19, 17, 5, 41, 9, 43, 11, 7, 23, 47, 3, 7, 5, 23, 13, 53, 3, 17, 7, 25, 29, 59, 7, 61, 31, 9, 2, 31, 15, 67, 17, 31, 17, 71, 3, 73, 37, 7, 19, 31, 17, 79, 5, 3

Offset: 1

Author

Jud McCranie

Keywords

• nonn

Comments

a(n)=p(n) if n=p(n); a(n) is not always A006530(n). - Labos Elemer, May 03 2002

This sequence is the Mobius transform of A087073. Let m be the squarefree part of n, then a(n) = a(m). When n = pq, the product of two distinct odd primes, then there is a formula for a(pq). Let x = 1/p (mod q) and y = 1/q (mod p). Then a(pq) = 2xy-1. There are also formulas for the number of positive and negative terms. See papers by Carlitz or Lam and Leung. - T. D. Noe, Aug 08 2003

Examples

			9th cyclotomic polynomial is x^6+x^3+1 which has 3 terms, so a(9)=3.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• L. Carlitz, Number of terms in the cyclotomic polynomial F(pq,x), Amer. Math. Monthly, Vol. 73, No. 9, 1966, pp. 979-981.
• T. Y. Lam and K. H. Leung, On the Cyclotomic Polynomial Phi(pq,x), Amer. Math. Monthly, Vol. 103, No. 7, 1996, pp. 562-564.
• Eric Weisstein's World of Mathematics, Cyclotomic Polynomial

Crossrefs

Cf. A086765 (number of positive terms in n-th cyclotomic polynomial), A086780 (number of negative terms in n-th cyclotomic polynomial), A086798 (number of zero terms in n-th cyclotomic polynomial), A087073.

Programs

Maple

A051664 := proc(n)
        numtheory[cyclotomic](n,x) ;
        nops([coeffs(%)]) ;
end proc: # R. J. Mathar, Sep 15 2012

Mathematica

Table[Count[CoefficientList[Cyclotomic[n, x], x], _?(#!=0&)], {n, 0, 100}]
Table[Length[Cyclotomic[n, x]], {n, 1, 100}] (* Artur Jasinski, Jan 15 2007 *)

PARI

a(n)=sum(k=0,eulerphi(n),if(polcoeff(polcyclo(n),k),1,0))

PARI

a(n) = #select(x->x!=0, Vec(polcyclo(n))); \\ Michel Marcus, Mar 05 2017

Formula

a(n) = phi(n) + 1 - A086798(n). - T. D. Noe, Aug 08 2003

Extensions

More terms from Labos Elemer, May 03 2002