A096223 - OEIS

%I #15 Oct 26 2019 22:32:03

%S 1,1,3,4,11,8,29,26,52,49,138,79,271,198,337,389,914,477,1596,993,

%T 1881,1912,4507,2222,6485,5080,8682,7384,18459,6780,28628,19598,31098,

%U 29444,53198,30470,99132,65771,104464,80422,215307,81792,313064,195091,272503

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

%C 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.

%e 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.

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

%o (PARI) a(n) = {my(s=0, k=1); while(k< n + 1, if(gcd(k,n)==1, s+=numbpart(k)); k++); s};

%o for(n=1, 45, print1(a(n),", ")) \\ _Indranil Ghosh_, Mar 16 2017

%Y Cf. A008683.

%K nonn,easy

%O 1,3

%A _Leroy Quet_, Jul 29 2004

%E Edited and extended by _Robert G. Wilson v_, Jul 29 2004