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,2

Comments

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

Links

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

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)

Example

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.

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 *)

Crossrefs

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

Sequence in context: A282098 A034760 A070639 * A364808 A187753 A339638

Adjacent sequences: A078389 A078390 A078391 * A078393 A078394 A078395

Keyword

nonn

Author

Vladeta Jovovic, Dec 24 2002

Status

approved