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

Author

Ilya Gutkovskiy, Jan 30 2020

Keywords

• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to partitions

Crossrefs

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

Programs

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}]

Formula

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