A065795 - OEIS

%I #39 Feb 22 2023 18:03:47

%S 1,2,4,6,10,16,26,42,72,124,218,390,706,1292,2388,4436,8292,15578,

%T 29376,55592,105532,200858,383220,732756,1403848,2694404,5179938,

%U 9973430,19229826,37125562,71762396,138871260,269021848,521666984,1012520400,1966957692,3824240848

%N Number of subsets of {1,2,...,n} that contain the average of their elements.

%C Also the number of subsets of {1,2,...,n} with sum of entries divisible by the largest element (compare A000016). See the Palmer Melbane link for a bijection. - _Joel B. Lewis_, Nov 13 2014

%H Alois P. Heinz, <a href="/A065795/b065795.txt">Table of n, a(n) for n = 1..3333</a>

%H Palmer Melbane, <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?p=3631416#p3631416">Art of Problem Solving thread</a>. - _Joel B. Lewis_, Nov 13 2014

%F a(n) = (1/2)*Sum_{i=1..n} (f(i) - 1) where f(i) = (1/i) * Sum_{d | i and d is odd} 2^(i/d) * phi(d).

%F a(n) = (n + A051293(n))/2.

%F a(n) = 2^n - A327471(n). - _Gus Wiseman_, Sep 14 2019

%e a(4)=6, since {1}, {2}, {3}, {4}, {1,2,3} and {2,3,4} contain their averages.

%e From _Gus Wiseman_, Sep 14 2019: (Start)

%e The a(1) = 1 through a(6) = 16 subsets:

%e   {1}  {1}  {1}      {1}      {1}          {1}

%e        {2}  {2}      {2}      {2}          {2}

%e             {3}      {3}      {3}          {3}

%e             {1,2,3}  {4}      {4}          {4}

%e                      {1,2,3}  {5}          {5}

%e                      {2,3,4}  {1,2,3}      {6}

%e                               {1,3,5}      {1,2,3}

%e                               {2,3,4}      {1,3,5}

%e                               {3,4,5}      {2,3,4}

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

%e                                            {3,4,5}

%e                                            {4,5,6}

%e                                            {1,2,3,6}

%e                                            {1,4,5,6}

%e                                            {1,2,3,4,5}

%e                                            {2,3,4,5,6}

%e (End)

%t Table[ Sum[a = Select[Divisors[i], OddQ[ # ] &]; Apply[ Plus, 2^(i/a) * EulerPhi[a]]/i, {i, n}]/2, {n, 34}]

%t (* second program *)

%t Table[Length[Select[Subsets[Range[n]],MemberQ[#,Mean[#]]&]],{n,0,10}] (* _Gus Wiseman_, Sep 14 2019 *)

%o (PARI) a(n) = (1/2)*sum(i=1, n, (1/i)*sumdiv(i, d, if (d%2, 2^(i/d)*eulerphi(d)))); \\ _Michel Marcus_, Dec 20 2020

%o (Python)

%o from sympy import totient, divisors

%o def A065795(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))>>1 # _Chai Wah Wu_, Feb 22 2023

%Y Subsets containing n whose mean is an element are A000016.

%Y The version for integer partitions is A237984.

%Y Subsets not containing their mean are A327471.

%Y Cf. A051293, A063776, A066571, A135342, A324736, A325705, A326083, A326836, A327478, A327481.

%K nonn

%O 1,2

%A _John W. Layman_, Dec 05 2001

%E Edited and extended by _Robert G. Wilson v_, Nov 15 2002