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,1

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)

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.

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

Example

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 + ...

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 *)

Prog

(PARI) {a(n) = if( n<1, 0, 1 / n * sumdiv( n, d, (d % 2) * eulerphi(d) * 2^(n / d)))}; /* Michael Somos, May 09 2013 */
(Haskell)
a063776 n = a053636 n `div` n  -- Reinhard Zumkeller, Sep 13 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//d-1 for d in divisors(n>>(~n&n-1).bit_length(), generator=True))<<1)//n # Chai Wah Wu, Feb 21 2023

Crossrefs

The superdiagonal of A068009.

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

Cf. A000016, A065795, A327475, A327481.

Sequence in context: A307240 A000013 A064484 * A287135 A276063 A247181

Adjacent sequences: A063773 A063774 A063775 * A063777 A063778 A063779

Keyword

nonn,nice

Author

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

Extensions

More terms from Vladeta Jovovic, Aug 20 2001

Status

approved