A078392 Sum of GCD's of parts in all partitions of n.

1, 3, 5, 9, 11, 20, 21, 35, 42, 61, 66, 112, 113, 168, 210, 279, 313, 461, 508, 719, 852, 1088, 1277, 1756, 2006, 2573, 3106, 3937, 4593, 5958, 6872, 8676, 10305, 12655, 15009, 18664, 21673, 26559, 31447, 38217, 44623, 54386, 63303, 76379, 89696, 106879

Offset: 1

Author

Vladeta Jovovic, Dec 24 2002

Keywords

• nonn

Comments

Equals row sums of triangle A168534. - Gary W. Adamson, Nov 28 2009

Examples

			Partitions of 4 are 1+1+1+1, 1+1+2, 2+2, 1+3, 4, the corresponding GCD's of parts are 1,1,2,1,4 and their sum is a(4) = 9.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A000010, A000041, A168534, A181844 (the same for LCM), A319301.

Programs

Maple

with(numtheory): with(combinat):
a:= n-> add(phi(n/d)*numbpart(d), d=divisors(n)):
seq(a(n), n=1..50);  # Alois P. Heinz, Apr 02 2015

Mathematica

a[n_] := Sum[EulerPhi[n/d]*PartitionsP[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Jul 01 2015, after Alois P. Heinz *)

Formula

a(n) = Sum_{d|n} d * A000837(n/d).

a(n) = Sum_{d|n} phi(n/d)*numbpart(d) = Sum_{d|n} A000010(n/d)*A000041(d). - Vladeta Jovovic, May 08 2003

From Richard L. Ollerton, May 06 2021: (Start)

a(n) = Sum_{k=1..n} A000041(gcd(n,k)).

a(n) = Sum_{k=1..n} A000041(n/gcd(n,k))*A000010(gcd(n,k))/A000010(n/gcd(n,k)). (End)