A096223 Let p(k) be the number of partitions of k (A000041); a(n) = Sum_{1<=k<=n, gcd(k,n)=1} p(k).

1, 1, 3, 4, 11, 8, 29, 26, 52, 49, 138, 79, 271, 198, 337, 389, 914, 477, 1596, 993, 1881, 1912, 4507, 2222, 6485, 5080, 8682, 7384, 18459, 6780, 28628, 19598, 31098, 29444, 53198, 30470, 99132, 65771, 104464, 80422, 215307, 81792, 313064, 195091, 272503

Offset

1,3

Comments

If we let mu() be the Moebius function (A008683), then a(n) = sum mu(j), where j is taken over all parts, with repetitions, of every partition of n and where each j is such that j|n.

Links

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

Example

The 7 partitions of 5 are 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 2+3, 1+4, 5. Of these parts, only 1 and 5 divide 5. Since there are twelve 1's and one 5, we have a(5) = 12*mu(1) + 1*mu(5) = 11.

Mathematica

f[n_] := Block[{s = 0, k = 1}, While[k < n + 1, If[ GCD[k, n] == 1, s = s + PartitionsP[k]]; k++ ]; s]; Table[ f[n], {n, 45}] (* Robert G. Wilson v, Jul 29 2004 *)

Prog

(PARI) a(n) = {my(s=0, k=1); while(k< n + 1, if(gcd(k, n)==1, s+=numbpart(k)); k++); s};
for(n=1, 45, print1(a(n), ", ")) \\ Indranil Ghosh, Mar 16 2017

Crossrefs

Cf. A008683.

Sequence in context: A220848 A370605 A232891 * A232862 A344460 A195589

Adjacent sequences: A096220 A096221 A096222 * A096224 A096225 A096226

Keyword

nonn,easy

Author

Leroy Quet, Jul 29 2004

Extensions

Edited and extended by Robert G. Wilson v, Jul 29 2004

Status

approved