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

1, 1, 2, 3, 6, 7, 13, 16, 23, 29, 42, 49, 69, 83, 102, 126, 161, 191, 239, 281, 336, 402, 484, 566, 672, 787, 919, 1067, 1251, 1449, 1684, 1934, 2223, 2554, 2920, 3341, 3821, 4344, 4928, 5586, 6334, 7163, 8091, 9100, 10228, 11492, 12902, 14449, 16167, 18058

Offset: 1

Author

Gus Wiseman, May 17 2018

Keywords

• nonn

Comments

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.

Examples

			The a(6) = 7 integer partitions of 6 whose distinct parts are pairwise coprime are (51), (411), (321), (3111), (2211), (21111), (111111).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500

Crossrefs

Cf. A000005, A007359, A007360, A018783, A051424, A078374, A101268, A289508, A289509, A302569, A302696, A302698, A302796, A302797, A304711, A304712.

Programs

Mathematica

Table[Select[IntegerPartitions[n],CoprimeQ@@Union[#]&]//Length,{n,20}]

PARI

lista(nn)={local(Cache=Map());
  my(excl=vector(nn, n, sum(i=1, n-1, if(gcd(i,n)>1, 2^(n-i)))));
  my(c(n, m, b)=
     if(n==0, 1,
        while(m>n || bittest(b,0), m--; b>>=1);
        my(hk=[n, m, b], z);
        if(!mapisdefined(Cache, hk, &z),
          z = if(m, self()(n, m-1, b>>1) + self()(n-m, m, bitor(b, excl[m])), 0);
          mapput(Cache, hk, z)); z));
  my(a(n)=c(n, n, 0) + 1 - numdiv(n));
  for(n=1, nn, print1(a(n), ", "))
} \\ Andrew Howroyd, Nov 02 2019

Formula

a(n) = A304712(n) + 1 - A000005(n). - Andrew Howroyd, Nov 02 2019