A063776 Number of subsets of {1,2,...,n} which sum to 0 modulo n.

2, 2, 4, 4, 8, 12, 20, 32, 60, 104, 188, 344, 632, 1172, 2192, 4096, 7712, 14572, 27596, 52432, 99880, 190652, 364724, 699072, 1342184, 2581112, 4971068, 9586984, 18512792, 35791472, 69273668, 134217728, 260301176, 505290272, 981706832

Offset: 1

Author

Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 16 2001

Keywords

• nonn
• nice

Comments

From Gus Wiseman, Sep 14 2019: (Start)

Also the number of subsets of {1..n} that are empty or contain n and have integer mean. If the subsets are not required to contain n, we get A327475. For example, the a(1) = 2 through a(6) = 12 subsets are:

{} {} {} {} {} {}

{1} {2} {3} {4} {5} {6}

{1,3} {2,4} {1,5} {2,6}

{1,2,3} {2,3,4} {3,5} {4,6}

{1,3,5} {1,2,6}

{3,4,5} {1,5,6}

{1,2,4,5} {2,4,6}

{1,2,3,4,5} {4,5,6}

{1,2,3,6}

{1,4,5,6}

{2,3,5,6}

{2,3,4,5,6}

(End)

Examples

			G.f. = 2*x + 2*x^2 + 4*x^3 + 4*x^4 + 8*x^5 + 12*x^6 + 20*x^7 + 32*x^8 + 60*x^9 + ...
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..3333 (first 200 terms from T. D. Noe)
• T. Amdeberhan, M. Can and V. Moll, Broken bracelets, Molien series, paraffin wax and the elliptic curve 48a4, SIAM Journal of Discrete Math., v.25, 2011, p. 1843. See equation (1.2).
• Juhani Karhumäki, S. Puzynina, M. Rao, and M. A. Whiteland, On cardinalities of k-abelian equivalence classes, arXiv preprint arXiv:1605.03319 [math.CO], 2016.
• N. Kitchloo and L. Pachter, An interesting result about subset sums, preprint (pdf file), 1993.
• N. Kitchloo and L. Pachter, An interesting result about subset sums, preprint (pdf file), 1993.

Crossrefs

The superdiagonal of A068009.

Cf. A000010, A000013, A051293, A053633, A053634, A053636, A054539, A082550.

Cf. A000016, A065795, A327475, A327481.

Programs

Haskell

a063776 n = a053636 n `div` n  -- Reinhard Zumkeller, Sep 13 2013

Mathematica

Table[a = Select[ Divisors[n], OddQ[ # ] &]; Apply[Plus, 2^(n/a)*EulerPhi[a]]/n, {n, 1, 35}]
a[ n_] := If[ n < 1, 0, 1/n Sum[ Mod[ d, 2] EulerPhi[ d] 2^(n / d), {d, Divisors[ n]}]]; (* Michael Somos, May 09 2013 *)
Table[Length[Select[Subsets[Range[n]],#=={}||MemberQ[#,n]&&IntegerQ[Mean[#]]&]],{n,0,10}] (* Gus Wiseman, Sep 14 2019 *)

PARI

{a(n) = if( n<1, 0, 1 / n * sumdiv( n, d, (d % 2) * eulerphi(d) * 2^(n / d)))}; /* Michael Somos, May 09 2013 */

PARI

a(n) = sumdiv(n, d, (d%2)* 2^(n/d)*eulerphi(d))/n; \\ Michel Marcus, Feb 10 2016

Python

from sympy import totient, divisors
def A063776(n): return (sum(totient(d)<>(~n&n-1).bit_length(),generator=True))<<1)//n # Chai Wah Wu, Feb 21 2023

Formula

a(n) = (1/n) * Sum_{d divides n and d is odd} 2^(n/d) * phi(d).

a(n) = (1/n) * A053636(n). - Michael Somos, May 09 2013

a(n) = 2 * A000016(n).

For odd n, a(n) = A000031(n).

G.f.: -Sum_{m >= 0} (phi(2*m + 1)/(2*m + 1)) * log(1 - 2*x^(2*m + 1)). - Petros Hadjicostas, Jul 13 2019

a(n) = A082550(n) + 1. - Gus Wiseman, Sep 14 2019

Extensions

More terms from Vladeta Jovovic, Aug 20 2001