A327475 Number of subsets of {1..n} whose mean is an integer, where {} has mean 0.

1, 2, 3, 6, 9, 16, 27, 46, 77, 136, 239, 426, 769, 1400, 2571, 4762, 8857, 16568, 31139, 58734, 111165, 211044, 401695, 766418, 1465489, 2807672, 5388783, 10359850, 19946833, 38459624, 74251095, 143524762, 277742489, 538043664, 1043333935, 2025040766, 3933915349

Offset

0,2

Links

Table of n, a(n) for n=0..36.

Formula

a(n) = A051293(n) + 1.

Example

The a(0) = 1 through a(5) = 16 subsets:
  {}  {}   {}   {}       {}       {}
      {1}  {1}  {1}      {1}      {1}
           {2}  {2}      {2}      {2}
                {3}      {3}      {3}
                {1,3}    {4}      {4}
                {1,2,3}  {1,3}    {5}
                         {2,4}    {1,3}
                         {1,2,3}  {1,5}
                         {2,3,4}  {2,4}
                                  {3,5}
                                  {1,2,3}
                                  {1,3,5}
                                  {2,3,4}
                                  {3,4,5}
                                  {1,2,4,5}
                                  {1,2,3,4,5}

Maple

with(numtheory):
b:= n-> add(2^(n/d)*phi(d), d=select(x-> x::odd, divisors(n)))/n:
a:= proc(n) option remember; `if`(n=0, 1, b(n)-1+a(n-1)) end:
seq(a(n), n=0..36);  # Alois P. Heinz, Jan 13 2024

Mathematica

Table[Length[Select[Subsets[Range[n]], #=={}||IntegerQ[Mean[#]]&]], {n, 0, 10}]

Prog

(Python)
from sympy import totient, divisors
def A327475(n): return sum((sum(totient(d)<<k//d-1 for d in divisors(k>>(~k&k-1).bit_length(), generator=True))<<1)//k for k in range(1, n+1))-n+1 # Chai Wah Wu, Feb 22 2023

Crossrefs

If the subset is required to contain n, we get A063776.

Cf. A000016, A051293, A065795, A082550, A135342, A327474, A327481.

Sequence in context: A048810 A331680 A367205 * A017915 A114702 A026768

Adjacent sequences: A327472 A327473 A327474 * A327476 A327477 A327478

Keyword

nonn

Author

Gus Wiseman, Sep 13 2019

Status

approved