login
Number of distinct means of nonempty subsets of {1,...,n}.
12

%I #24 May 05 2023 11:20:31

%S 1,3,5,9,15,25,37,55,77,105,137,179,225,283,347,419,499,595,697,817,

%T 945,1085,1235,1407,1587,1787,1999,2229,2471,2741,3019,3327,3651,3995,

%U 4355,4739,5135,5567,6017,6491,6981,7511,8053,8637,9241,9869,10519,11215,11927,12681

%N Number of distinct means of nonempty subsets of {1,...,n}.

%H Alois P. Heinz, <a href="/A135342/b135342.txt">Table of n, a(n) for n = 1..10000</a>

%H R. J. Mathar, <a href="/A135342/a135342.pdf">Derivation of formula for 2nd differences</a>

%F a(n) = Sum_{k=1..n-1} [(n-k) * phi(k)] + min(n,2) = A103116(n-1)+ min(n,2); a(1)=1; a(2)=3; a(3)=5.

%F a(n) = 2*a(n-1) - a(n-2) + phi(n-1) for n>3.

%F a(n)-a(n-1) = A002088(n-1), n>=3. (Note the previous formula just says that the 2nd differences are A000010, and this is a trivial consequence.) - _R. J. Mathar_, Jan 27 2023

%e a(4) = 9: the possible means for a set drawn from {1, 2, 3, 4} are {1, 3/2, 2, 7/3, 5/2, 8/3, 3, 7/2, 4}.

%p a:= proc(n) option remember; `if`(n<4, [0, 1, 3, 5][n+1],

%p 2*a(n-1)-a(n-2)+numtheory[phi](n-1))

%p end:

%p seq(a(n), n=0..50); # _Alois P. Heinz_, Sep 13 2019

%t a[n_] := Sum[EulerPhi[k] (n - k), {k, 1, n - 1}] + Min[n, 2]

%o (PARI) M135342=List([1,3,5]);

%o A135342(n)=while(n>#M135342, listput(M135342, [-1,2]*Col(M135342[-2..-1])+eulerphi(#M135342))); M135342[n];

%o apply(A135342, [1..55]) \\ _M. F. Hasler_, Jan 24 2023

%o (Python)

%o from sympy import totient

%o def A135342(n, A=[1,3,5]):

%o while n>len(A): A.append(2*A[-1]-A[-2]+totient(len(A)))

%o return A[n-1] # _M. F. Hasler_, Jan 24 2023

%Y First differences are A002088, second differences A000010.

%K easy,nonn

%O 1,2

%A _Jacob A. Siehler_, Feb 16 2008