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

1, 3, 5, 9, 15, 25, 37, 55, 77, 105, 137, 179, 225, 283, 347, 419, 499, 595, 697, 817, 945, 1085, 1235, 1407, 1587, 1787, 1999, 2229, 2471, 2741, 3019, 3327, 3651, 3995, 4355, 4739, 5135, 5567, 6017, 6491, 6981, 7511, 8053, 8637, 9241, 9869, 10519, 11215, 11927, 12681

Offset: 1

Author

Jacob A. Siehler, Feb 16 2008

Keywords

• easy
• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• R. J. Mathar, Derivation of formula for 2nd differences

Crossrefs

First differences are A002088, second differences A000010.

Programs

Maple

a:= proc(n) option remember; `if`(n<4, [0, 1, 3, 5][n+1],
      2*a(n-1)-a(n-2)+numtheory[phi](n-1))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Sep 13 2019

Mathematica

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

PARI

M135342=List([1,3,5]);
A135342(n)=while(n>#M135342, listput(M135342, [-1,2]*Col(M135342[-2..-1])+eulerphi(#M135342))); M135342[n];
apply(A135342, [1..55]) \\ M. F. Hasler, Jan 24 2023

Python

from sympy import totient
def A135342(n, A=[1,3,5]):
    while n>len(A): A.append(2*A[-1]-A[-2]+totient(len(A)))
    return A[n-1] # M. F. Hasler, Jan 24 2023

Formula

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.

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

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