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

Links

Table of n, a(n) for n=1..41.

Formula

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

Example

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.

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

Prog

(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

Crossrefs

Cf. A000837.

Sequence in context: A342013 A213544 A265482 * A073118 A048082 A089089

Adjacent sequences: A085407 A085408 A085409 * A085411 A085412 A085413

Keyword

easy,nonn

Author

Vladeta Jovovic, Aug 13 2003

Extensions

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

Status

approved