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