login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A063776 Number of subsets of {1,2,...,n} which sum to 0 modulo n. 20
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 (list; graph; refs; listen; history; text; internal format)
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, 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

CROSSREFS

The super-diagonal 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 19:34 EDT 2021. Contains 347694 sequences. (Running on oeis4.)