A306275 Number of values 0 < k <= n for which there are no k distinct n-th roots of unity that sum to zero.

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 2, 12, 6, 8, 8, 16, 2, 18, 4, 12, 10, 22, 2, 20, 12, 18, 6, 28, 2, 30, 16, 20, 16, 24, 2, 36, 18, 24, 4, 40, 2, 42, 10, 8, 22, 46, 2, 42, 4, 32, 12, 52, 2, 40, 6, 36, 28, 58, 2, 60, 30, 12, 32, 48, 2, 66, 16, 44, 4, 70, 2, 72

Offset

1,3

Comments

In the first 17 terms a(n) = phi(n) except for n=12. For primes a(p) = p - 1.

Also the number of 0's in the n-th row of A103306. - Alois P. Heinz, Feb 03 2019

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Matt Baker, The Balanced Centrifuge Problem, Math Blog, 2018.

Holly Krieger and Brady Haran, The Centrifuge Problem, Numberphile video (2018)

T. Y. Lam and K. H. Leung, On vanishing sums for roots of unity, arXiv:math/9511209 [math.NT], 1995.

Gary Sivek, On vanishing sums of distinct roots of unity, #A31, Integers 10 (2010), 365-368.

Formula

a(n) = #{k in {1,2,...,n} | for all subsets U of {exp(2*Pi*i*m/n)|m=0,1,...,n-1} of size #U=k we have sum(U) != 0 }.

a(n) = 1 + n - A322366(n) for n > 1, a(1) = 1. - Alois P. Heinz, Feb 03 2019

a(n) is even for n >= 3. - Alois P. Heinz, Feb 05 2019

Maple

a:= proc(n) option remember; local f, b; f, b:=
       map(i-> i[1], ifactors(n)[2]),
       proc(m, i) option remember; m=0 or i>0 and
        (b(m, i-1) or f[i]<=m and b(m-f[i], i))
       end; forget(b); (t-> add(
      `if`(b(j, t) and b(n-j, t), 0, 1), j=1..n))(nops(f))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 03 2019

Mathematica

a := Function[{n}, Count[Function[{k}, Fold[And, (#!=0)& /@ RootReduce @* Total /@ Subsets[Exp[2*Pi*I*#/n]& /@ Range[0, n-1], {k}]]] /@ Range[1, n], True] ]
(* Second program: *)
A322366[n_] := A322366[n] = Module[{f, b}, f = FactorInteger[n][[All, 1]]; b[m_, i_] := b[m, i] = m == 0 || i > 0 && (b[m, i - 1] || f[[i]] <= m && b[m - f[[i]], i]); Function[t, Sum[If[b[j, t] && b[n - j, t], 1, 0], {j, 0, n}]][Length[f]]];
a[n_] := If[n == 1, 1, 1 + n - A322366[n]];
Array[a, 100] (* Jean-François Alcover, May 23 2020, after Alois P. Heinz *)

Crossrefs

Cf. A103306, A322366.

Sequence in context: A290077 A277030 A011773 * A322321 A080737 A152455

Adjacent sequences: A306272 A306273 A306274 * A306276 A306277 A306278

Keyword

nonn

Author

Florentin Bieder, Feb 03 2019

Extensions

More terms from Alois P. Heinz, Feb 03 2019

Status

approved