A345039 Number of partitions of n into two composite parts that share a nontrivial divisor.

0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 2, 1, 3, 0, 4, 0, 4, 2, 4, 0, 6, 1, 5, 3, 6, 0, 8, 0, 7, 4, 7, 3, 10, 0, 8, 5, 10, 0, 12, 0, 10, 8, 10, 0, 14, 2, 13, 7, 12, 0, 16, 5, 14, 8, 13, 0, 19, 0, 14, 11, 15, 6, 20, 0, 16, 10, 20, 0, 22, 0, 17, 15, 18, 6, 24, 0, 22, 12, 19, 0, 27

Offset: 1

Author

Wesley Ivan Hurt, Jun 06 2021

Keywords

• nonn

Examples

			a(12) = 2; (8,4) and (6,6).
a(15) = 1; (9,6).
a(16) = 3; (12,4), (10,6), and (8,8).
a(18) = 4; (14,4), (12,6), (10,8), and (9,9).
		

Crossrefs

Cf. A062610, A066247.

Programs

Mathematica

Table[Sum[(1 - PrimePi[k] + PrimePi[k - 1]) (1 - PrimePi[n - k] + PrimePi[n - k - 1]) (1 - Floor[1/GCD[k, n - k]]), {k, Floor[n/2]}], {n, 100}]

Formula

a(n) = Sum_{k=1..floor(n/2)} (1 - floor(1/gcd(k,n-k))) * c(k) * c(n-k), where c(n) is the characteristic function of composite numbers.