A063696 Positions of positive coefficients in cyclotomic polynomial Phi_n(x), converted from binary to decimal.

0, 2, 3, 7, 5, 31, 5, 127, 17, 73, 21, 2047, 17, 8191, 85, 297, 257, 131071, 65, 524287, 273, 4681, 1365, 8388607, 257, 1082401, 5461, 262657, 4369, 536870911, 387, 2147483647, 65537, 1198665, 87381, 17454241, 4097, 137438953471, 349525

Offset

0,2

Comments

Maple procedures Phi_pos_terms and Phi_neg_terms are modeled after the formula given in Lam and Leung paper and they compute correct results for all integers x > 1 and for all n with at most two distinct odd prime factors (that is, up to n=104). Other procedures as in A063698 and A063694.

Links

Table of n, a(n) for n=0..38.

D. M. Bloom, On the Coefficients of the Cyclotomic Polynomials, Amer.Math.Monthly 75, 372-377, 1968.

T. Y. Lam and K. H. Leung, On the Cyclotomic Polynomial Phi_pq(X), Amer.Math.Monthly 103, 562-564, August-September 1996.

H. W. Lenstra, Vanishing sums of roots of unity, in Proc. Bicentennial Congress Wiskundig Genootschap (Vrije Univ. Amsterdam, 1978), Part II, pp. 249-268.

Index entries for cyclotomic polynomials, positions of coefficients

Maple

with(numtheory); [seq(Phi_pos_terms(j, 2), j=0..104)];
inv_p_mod_q := (p, q) -> op(2, op(1, msolve(p*x=1, q))); # Find's p's inverse modulo q.
dilate := proc(nn, x, e) local n, i, s; n := nn; i := 0; s := 0; while(n > 0) do s := s + (((x^e)^i)*(n mod x)); n := floor(n/x); i := i+1; od; RETURN(s); end;
Phi_pos_terms := proc(n, x) local a, m, p, q, e, f, r, s; if(n < 2) then RETURN(x); fi; a := op(2, ifactors(n)); m := nops(a); p := a[1][1]; e := a[1][2]; if(1 = m) then RETURN(((x^(p^e))-1)/((x^(p^(e-1)))-1)); fi; if(2 = m) then q := a[2][1]; f := a[2][2]; r := inv_p_mod_q(p, q)-1; s := inv_p_mod_q(q, p)-1; RETURN( (`if`(0=s, 1, (((x^((s+1)*((q^f)*(p^(e-1)))))-1)/((x^((q^f)*(p^(e-1))))-1)))) * (`if`(0=r, 1, (((x^((r+1)*((p^e)*(q^(f-1)))))-1)/((x^((p^e)*(q^(f-1))))-1)))) ); fi; if((3 = m) and (2 = p)) then if(1 = e) then RETURN(every_other_pos(Phi_pos_terms(n/2, x), x, 0)+every_other_pos(Phi_neg_terms(n/2, x), x, 1)); else RETURN(dilate(Phi_pos_terms((n/(2^(e-1))), x), x, 2^(e-1))); fi; else printf(`Cannot handle argument %a with three or more distinct odd prime factors!\n`, n); RETURN(0); fi; end;

Mathematica

a[n_] := 2^(Flatten[Position[CoefficientList[Cyclotomic[n, x], x], _?Positive]] - 1) // Total; a[0] = 0; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 05 2016 *)

Prog

(PARI) a(n)=local(p); if(n<1, 0, p=polcyclo(n); sum(i=0, n, 2^i*(polcoeff(p, i)>0)))

Crossrefs

Cf. A013594, A063697 (binary version), A063698 (negative terms), A063670 (nonzero terms).

A019320(n) = a(n) - A063698(n) for up to n=104.

Sequence in context: A153488 A275115 A085399 * A258126 A332211 A353075

Adjacent sequences: A063693 A063694 A063695 * A063697 A063698 A063699

Keyword

nonn

Author

Antti Karttunen, Aug 03 2001

Status

approved