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,7

Links

Table of n, a(n) for n=0..70.

Index entries for sequences related to partitions

Formula

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

Example

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

Maple

a:= proc(m) option remember; local b; b:=
      proc(n, i) option remember; `if`(i*(i+1)/2<n, 0, `if`(n=0, 1,
        `if`(igcd(i, m)>1, 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}]

Crossrefs

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

Sequence in context: A131085 A303280 A318717 * A328220 A134192 A358344

Adjacent sequences: A331884 A331885 A331886 * A331888 A331889 A331890

Keyword

nonn

Author

Ilya Gutkovskiy, Jan 30 2020

Status

approved