cp's OEIS Frontend

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

%I A306275 #41 May 27 2022 02:06:32
%S A306275 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,
%T A306275 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,
%U A306275 40,6,36,28,58,2,60,30,12,32,48,2,66,16,44,4,70,2,72
%N A306275 Number of values 0 < k <= n for which there are no k distinct n-th roots of unity that sum to zero.
%C A306275 In the first 17 terms a(n) = phi(n) except for n=12. For primes a(p) = p - 1.
%C A306275 Also the number of 0's in the n-th row of A103306. - _Alois P. Heinz_, Feb 03 2019
%H A306275 Alois P. Heinz, <a href="/A306275/b306275.txt">Table of n, a(n) for n = 1..10000</a>
%H A306275 Matt Baker, <a href="https://mattbaker.blog/2018/06/25/the-balanced-centrifuge-problem/">The Balanced Centrifuge Problem</a>, Math Blog, 2018.
%H A306275 Holly Krieger and Brady Haran, <a href="https://www.youtube.com/watch?v=7DHE8RnsCQ8">The Centrifuge Problem</a>, Numberphile video (2018)
%H A306275 T. Y. Lam and K. H. Leung, <a href="https://arxiv.org/abs/math/9511209">On vanishing sums for roots of unity</a>, arXiv:math/9511209 [math.NT], 1995.
%H A306275 Gary Sivek, <a href="http://www.emis.de/journals/INTEGERS/papers/k31/k31.Abstract.html">On vanishing sums of distinct roots of unity</a>, #A31, Integers 10 (2010), 365-368.
%F A306275 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 }.
%F A306275 a(n) = 1 + n - A322366(n) for n > 1, a(1) = 1. - _Alois P. Heinz_, Feb 03 2019
%F A306275 a(n) is even for n >= 3. - _Alois P. Heinz_, Feb 05 2019
%p A306275 a:= proc(n) option remember; local f, b; f, b:=
%p A306275        map(i-> i[1], ifactors(n)[2]),
%p A306275        proc(m, i) option remember; m=0 or i>0 and
%p A306275         (b(m, i-1) or f[i]<=m and b(m-f[i], i))
%p A306275        end; forget(b); (t-> add(
%p A306275       `if`(b(j, t) and b(n-j, t), 0, 1), j=1..n))(nops(f))
%p A306275     end:
%p A306275 seq(a(n), n=1..100);  # _Alois P. Heinz_, Feb 03 2019
%t A306275 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] ]
%t A306275 (* Second program: *)
%t A306275 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]]];
%t A306275 a[n_] := If[n == 1, 1, 1 + n - A322366[n]];
%t A306275 Array[a, 100] (* _Jean-François Alcover_, May 23 2020, after _Alois P. Heinz_ *)
%Y A306275 Cf. A103306, A322366.
%K A306275 nonn
%O A306275 1,3
%A A306275 _Florentin Bieder_, Feb 03 2019
%E A306275 More terms from _Alois P. Heinz_, Feb 03 2019