cp's OEIS Frontend

A057562 Number of partitions of n into parts all relatively prime to n.

%I A057562 #36 Apr 16 2025 04:54:04
%S A057562 1,1,2,2,6,2,14,6,16,7,55,6,100,17,44,32,296,14,489,35,178,77,1254,30,
%T A057562 1156,147,731,142,4564,25,6841,390,1668,474,4780,114,21636,810,4362,
%U A057562 432,44582,103,63260,1357,4186,2200,124753,364,105604,1232,24482,3583
%N A057562 Number of partitions of n into parts all relatively prime to n.
%C A057562 p is prime iff a(p) = A000041(p)-1. - _Lior Manor_, Feb 04 2005
%H A057562 Charles R Greathouse IV, <a href="/A057562/b057562.txt">Table of n, a(n) for n = 1..1000</a>
%F A057562 Coefficient of x^n in expansion of 1/Product_{d : gcd(d, n)=1} (1-x^d). - _Vladeta Jovovic_, Dec 23 2004
%e A057562 The unrestricted partitions of 4 are 1+1+1+1, 1+1+2, 1+3, 2+2 and 4. Of these, only 1+1+1+1 and 1+3 contain parts which are all relatively prime to 4. So a(4) = 2.
%t A057562 Table[Count[IntegerPartitions@ n, k_ /; AllTrue[k, CoprimeQ[#, n] &]], {n, 52}] (* _Michael De Vlieger_, Aug 01 2017 *)
%o A057562 (PARI) R(n, v)=if(#v<2 || n<v[2], n>=0, sum(i=1, #v, R(n-v[i], v[1..i])))
%o A057562 a(n)=if(isprime(n), return(numbpart(n)-1)); R(n, select(k->gcd(k, n)==1, vector(n, i, i))) \\ _Charles R Greathouse IV_, Sep 13 2012
%o A057562 (PARI) a(n)=polcoeff(1/prod(k=1,n,if(gcd(k,n)==1,1-x^k,1), O(x^(n+1))+1), n) \\ _Charles R Greathouse IV_, Sep 13 2012
%o A057562 (Haskell)
%o A057562 a057562 n = p (a038566_row n) n where
%o A057562    p _          0 = 1
%o A057562    p []         _ = 0
%o A057562    p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
%o A057562 -- _Reinhard Zumkeller_, Jul 05 2013
%Y A057562 Cf. A036998, A038566, A100347, A227296.
%Y A057562 See also A098743 (parts don't divide n).
%K A057562 nonn
%O A057562 1,3
%A A057562 _Leroy Quet_, Oct 03 2000
%E A057562 More terms from _Naohiro Nomoto_, Feb 28 2002
%E A057562 Corrected by _Vladeta Jovovic_, Dec 23 2004