A322366 Number of integers k in {0,1,...,n} such that k identical test tubes can be balanced in a centrifuge with n equally spaced holes.

1, 0, 2, 2, 3, 2, 5, 2, 5, 4, 7, 2, 11, 2, 9, 8, 9, 2, 17, 2, 17, 10, 13, 2, 23, 6, 15, 10, 23, 2, 29, 2, 17, 14, 19, 12, 35, 2, 21, 16, 37, 2, 41, 2, 35, 38, 25, 2, 47, 8, 47, 20, 41, 2, 53, 16, 51, 22, 31, 2, 59, 2, 33, 52, 33, 18, 65, 2, 53, 26, 67, 2, 71, 2, 39, 68, 59, 18, 77, 2, 77, 28, 43, 2, 83, 22, 45, 32, 79

Offset: 0

Author

Alois P. Heinz, Dec 04 2018

Keywords

• nonn
• look

Comments

Numbers where a(n) + A000010(n) != n + 1: A102467. - Robert G. Wilson v, Aug 23 2021

Examples

			a(6) = |{0,2,3,4,6}| = 5.
a(9) = |{0,3,6,9}| = 4.
a(10) = |{0,2,4,5,6,8,10}| = 7.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..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.
• Robert G. Wilson v, Graph of the first 100001 terms.

Crossrefs

Cf. A000040, A001248, A001748, A001750, A004280, A008588, A008864, A100484, A103306, A103314, A163300, A182986, A272470, A306275.

Programs

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), 1, 0), j=0..n))(nops(f))
    end:
seq(a(n), n=0..100);

Mathematica

$RecursionLimit = 4096;
a[1] = 0;
a[n_] := a[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]);
     With[{t = Length[f]}, Sum[
     If[b[j, t] && b[n - j, t], 1, 0], {j, 0, n}]]];
Table[a[n], {n, 0, 1000}] (* Jean-François Alcover, Dec 13 2018, after Alois P. Heinz, corrected and updated Aug 07 2021 *)
f[n_] := Block[{c = 2, k = 2, p = First@# & /@ FactorInteger@ n}, While[k < n, If[ IntegerPartitions[k, All, p, 1] != {} && IntegerPartitions[n - k, All, p, 1] != {}, c++]; k++]; c]; f[0] = 1; f[1] = 0; Array[f, 75] (* Robert G. Wilson v, Aug 22 2021 *)

Formula

a(n) = |{ k : k and n-k can be written as a sum of prime factors of n }|.

a(n) = 2 <=> n is prime (A000040).

a(n) >= n-1 <=> n in {1,2,3,4} union { A008588 }.

a(n) = (n+4)/2 <=> n in { A100484 } minus { 4 }.

a(n) = (n+9)/3 <=> n in { A001748 } minus { 9 }.

a(n) = (n+25)/5 <=> n in { A001750 } minus { 25 }.

a(n) = (n+49)/7 <=> n in { A272470 } minus { 49 }.

a(n^2) = n+1 <=> n = 0 or n is prime <=> n in { A182986 }.

a(A001248(n)) = A008864(n).

a(n) is odd <=> n in { A163300 }.

a(n) is even <=> n in { A004280 }.