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

1, 0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 16, 9, 22, 1, 51, 1, 51, 17, 57, 1, 147, 7, 102, 30, 152, 1, 620, 1, 231, 58, 298, 21, 946, 1, 491, 103, 921, 1, 3249, 1, 1060, 325, 1256, 1, 4866, 15, 3157, 299, 2539, 1, 10369, 62, 4846, 492, 4566, 1, 45786, 1, 6843

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for sequences related to partitions

Formula

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

Example

a(6) = 4 because we have [6], [4, 2], [3, 3] and [2, 2, 2].

Maple

a:= proc(m) option remember; local b; b:=
      proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
       `if`(igcd(i, m)>1, b(n-i, min(i, 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/(1 - Boole[GCD[k, n] > 1] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 62}]

Crossrefs

Cf. A182986 (positions of 1's), A018783, A057562, A121998, A331887, A331888.

Sequence in context: A018783 A200976 A328187 * A298971 A328602 A218970

Adjacent sequences: A331882 A331883 A331884 * A331886 A331887 A331888

Keyword

nonn

Author

Ilya Gutkovskiy, Jan 30 2020

Status

approved