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

Author

Gus Wiseman, Sep 13 2019

Keywords

• nonn

Examples

			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}
		

Crossrefs

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

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

Programs

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}]

Python

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

Formula

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