A085410 Total number of parts in all partitions of n into relatively prime parts.

1, 2, 5, 9, 19, 27, 53, 74, 122, 170, 274, 355, 555, 724, 1043, 1377, 1964, 2487, 3497, 4429, 5993, 7622, 10205, 12701, 16831, 20964, 27166, 33756, 43452, 53296, 68134, 83464, 105086, 128495, 160803, 195006, 242811, 293701, 362026, 436842, 536103

Offset: 1

Author

Vladeta Jovovic, Aug 13 2003

Keywords

• easy
• nonn

Examples

			Partitions of 6 into relatively prime parts are: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+2+2, 1+1+1+3, 1+2+3, 1+1+4, 1+5; total number of parts is a(6)=6+5+4+4+3+3+2=27.
		

Crossrefs

Cf. A000837, A006128.

Programs

Mathematica

f[n_] := Sum[DivisorSigma[0, m] PartitionsP[n - m], {m, 1, n}]; MT[n_] := Block[{d = Divisors[n]}, Plus @@ (MoebiusMu /@ (n/d)*f /@ d)]; Table[ MT[n], {n, 1, 41}]

PARI

a006128(n) = sum(m=1, n, numdiv(m)*numbpart(n - m));
a(n) = sumdiv(n, d, moebius(n/d)*a006128(d)); \\ Indranil Ghosh, Apr 25 2017

Python

from sympy import divisors, divisor_count, npartitions, mobius
def a006128(n): return sum([divisor_count(m)*npartitions(n - m) for m in range(1, n + 1)])
def a(n): return sum([mobius(n/d)*a006128(d) for d in divisors(n)]) # Indranil Ghosh, Apr 25 2017

Formula

Moebius transform of A006128: Sum_{d|n} mu(n/d)*A006128(d).

Extensions

More terms from Robert G. Wilson v, Aug 17 2003