A331887 Number of partitions of n into distinct parts having a common factor > 1 with n.

1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 3, 1, 5, 1, 5, 4, 6, 1, 11, 1, 11, 6, 12, 1, 23, 3, 18, 8, 23, 1, 69, 1, 32, 13, 38, 7, 84, 1, 54, 19, 79, 1, 224, 1, 90, 46, 104, 1, 264, 5, 187, 39, 166, 1, 449, 14, 251, 55, 256, 1, 1374, 1, 340, 111, 390, 20, 1692, 1, 513, 105, 1610

Offset: 0

Author

Ilya Gutkovskiy, Jan 30 2020

Keywords

• nonn

Examples

			a(12) = 5 because we have [12], [10, 2], [9, 3], [8, 4] and [6, 4, 2].
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..10416
• Index entries for sequences related to partitions

Crossrefs

Cf. A036998, A121998, A175787 (positions of 1's), A303280, A331885, A331888.

Programs

Maple

a:= proc(m) option remember; local b; b:=
      proc(n, i) option remember; `if`(i*(i+1)/21, b(n-i, min(i-1, n-i)), 0)+b(n, i-1)))
      end; forget(b); b(m$2)
    end:
seq(a(n), n=0..82);  # Alois P. Heinz, Jan 30 2020

Mathematica

Table[SeriesCoefficient[Product[(1 + Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 70}]

PARI

A331887(n) = { my(p = Ser(1, 'x, 1+n)); for(k=2, n, if(gcd(n,k)>1, p *= (1 + 'x^k))); polcoef(p, n); }; \\ Antti Karttunen, Jan 25 2025

Formula

a(n) = [x^n] Product_{k: gcd(n,k) > 1} (1 + x^k).