A164896 Number of subsets (up to cyclic shifts) of the n-th roots of 1 with zero sum.

1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 2, 19, 2, 21, 10, 36, 2, 94, 2, 117, 22, 189, 2, 618, 8, 633, 60, 1203, 2, 6069, 2, 4116, 190, 7713, 26, 35324, 2, 27597, 634, 59706, 2, 328835, 2, 190935, 2728, 364725, 2, 2435780, 20, 1579884, 7714, 2582061, 2, 21013770, 194, 9894294, 27598, 18512793, 2, 377367015, 2, 69273669, 104832, 134219796, 638, 1678410951

Offset: 1

Author

Joerg Arndt, Aug 30 2009

Keywords

• nonn

Comments

Cyclic shifts correspond to multiplication by a root of unity.

a(n)=2 for n prime, corresponding to the empty and the full subset. - Joerg Arndt, Jun 10 2011

Examples

			a(6) = 5 because these subsets add to zero: (left: as bitstring, right: subset)
  ......  (empty sum)
  ..1..1  0 3
  .1.1.1  0 2 4
  .11.11  0 1 3 4
  111111  0 1 2 3 4 5 (all roots of unity)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..164
• Joerg Arndt, Matters Computational (The Fxtbook), section 18.4 "Sums of roots of unity that are zero", p. 383.

Crossrefs

Cf. A066656, A103314, A110981 (counts subsets with bitstrings being Lyndon words).

Formula

a(n) = A110981(n) + Sum_{d|n,dA001037(d) = A110981(n) + A000031(n) - A001037(n). - Max Alekseyev, Apr 08 2013

a(n) = A110981(n) + A066656(n). - Andrew Howroyd, Mar 22 2023

Extensions

a(32)-a(39) from Joerg Arndt, Jun 10 2011

Terms a(40) onward from Max Alekseyev, Apr 08 2013