|
|
A304709
|
|
Number of integer partitions of n whose distinct parts are pairwise coprime.
|
|
21
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
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.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
The a(6) = 7 integer partitions of 6 whose distinct parts are pairwise coprime are (51), (411), (321), (3111), (2211), (21111), (111111).
|
|
MATHEMATICA
|
Table[Select[IntegerPartitions[n], CoprimeQ@@Union[#]&]//Length, {n, 20}]
|
|
PROG
|
(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), ", "))
|
|
CROSSREFS
|
Cf. A000005, A007359, A007360, A018783, A051424, A078374, A101268, A289508, A289509, A302569, A302696, A302698, A302796, A302797, A304711, A304712.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|