cp's OEIS Frontend

A304709 Number of integer partitions of n whose distinct parts are pairwise coprime.

%I A304709 #15 Nov 02 2019 19:59:11
%S A304709 1,1,2,3,6,7,13,16,23,29,42,49,69,83,102,126,161,191,239,281,336,402,
%T A304709 484,566,672,787,919,1067,1251,1449,1684,1934,2223,2554,2920,3341,
%U A304709 3821,4344,4928,5586,6334,7163,8091,9100,10228,11492,12902,14449,16167,18058
%N A304709 Number of integer partitions of n whose distinct parts are pairwise coprime.
%C A304709 Two parts are coprime if they have no common divisor greater than 1. For partitions of length 1 note that (1) is coprime but (x) is not coprime for x > 1.
%H A304709 Andrew Howroyd, <a href="/A304709/b304709.txt">Table of n, a(n) for n = 1..500</a>
%F A304709 a(n) = A304712(n) + 1 - A000005(n). - _Andrew Howroyd_, Nov 02 2019
%e A304709 The a(6) = 7 integer partitions of 6 whose distinct parts are pairwise coprime are (51), (411), (321), (3111), (2211), (21111), (111111).
%t A304709 Table[Select[IntegerPartitions[n],CoprimeQ@@Union[#]&]//Length,{n,20}]
%o A304709 (PARI)
%o A304709 lista(nn)={local(Cache=Map());
%o A304709   my(excl=vector(nn, n, sum(i=1, n-1, if(gcd(i,n)>1, 2^(n-i)))));
%o A304709   my(c(n, m, b)=
%o A304709      if(n==0, 1,
%o A304709         while(m>n || bittest(b,0), m--; b>>=1);
%o A304709         my(hk=[n, m, b], z);
%o A304709         if(!mapisdefined(Cache, hk, &z),
%o A304709           z = if(m, self()(n, m-1, b>>1) + self()(n-m, m, bitor(b, excl[m])), 0);
%o A304709           mapput(Cache, hk, z)); z));
%o A304709   my(a(n)=c(n, n, 0) + 1 - numdiv(n));
%o A304709   for(n=1, nn, print1(a(n), ", "))
%o A304709 } \\ _Andrew Howroyd_, Nov 02 2019
%Y A304709 Cf. A000005, A007359, A007360, A018783, A051424, A078374, A101268, A289508, A289509, A302569, A302696, A302698, A302796, A302797, A304711, A304712.
%K A304709 nonn
%O A304709 1,3
%A A304709 _Gus Wiseman_, May 17 2018